Code Submission Evaluation System Login

CSES - HIIT Open 2018

HIIT Open 2018

Contest start:2018-05-26 11:00:00
Contest end:2018-05-26 16:00:00

Task list | Submit code | Submissions | Messages | Scoreboard | Statistics


History
2018-05-26 14:16:19
2018-05-26 14:00:13
Task:Buy Low, Sell High
Sender:Oispa nutellaa
Submission time:2018-05-26 14:16:19
Status:READY
Result:ACCEPTED

Show test data

Code

#include <iostream>

using namespace std;
typedef long long ll;

int n;
ll t[500005];
ll dp[500005];

ll res = 0;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> t[i];
	}
	ll cmi = 1000000005;
	for (int i = 0; i < n; ++i) {
		cmi = min(t[i], cmi);
		dp[i] = t[i]-cmi;
		if (i > 0) dp[i] = max(dp[i], dp[i-1]);
	}
	ll cmx = 0;
	ll rb = 0;
	for (int i = n-1; i >= 0; --i) {
		cmx = max(t[i], cmx);
		ll cr = cmx-t[i];
		rb = max(rb, cr);
		res = max(res, dp[i]+rb);
	}
	cout << res << "\n";
	return 0;
}