torus711 のアレ

主に競技プログラミングの問題について書きます

Codeforces #226, A : Bear and Raspberry

概要

 ある品物があり、i 日目には A 一つが金額 x_i で売れる。
 くまは始め、一つの品物も持っていないが、金額 c を上乗せして返すことを条件に品物を一つ友人から借りる。くまがとる戦略は、有効な d について、d 日目に品物を売ってから ( d + 1 ) 日目に買い戻し、差額で利益を得るというものである。
 くまが得ることのできる利益の最大値を求めよ。

解法

 d が決まったとき、そのときの利益は x_d - x_{ d + 1 } - c と計算されます。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;
}