概要
ある品物があり、i 日目には A 一つが金額 で売れる。
くまは始め、一つの品物も持っていないが、金額 c を上乗せして返すことを条件に品物を一つ友人から借りる。くまがとる戦略は、有効な d について、d 日目に品物を売ってから ( d + 1 ) 日目に買い戻し、差額で利益を得るというものである。
くまが得ることのできる利益の最大値を求めよ。
解法
d が決まったとき、そのときの利益は と計算されます。d を全て試して最大のものを探すことで答えが求まります。
コード
typedef vector<int> VI; #define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i ) #define FOR( v, c ) for ( auto &v : c ) #define ALL( c ) (c).begin(), (c).end() int main() { cin.tie( 0 ); ios::sync_with_stdio( false ); int n, c; cin >> n >> c; VI as( n ); FOR( a, as ) { cin >> a; } int res = 0; REP( i, 0, n - 1 ) { res = max( res, as[i] - as[ i + 1 ] - c ); } cout << res << endl; return 0; }