Submission #998981

#	Time	Username	Problem	Language	Result	Execution time	Memory
998981		Angus_Yeung	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	23 ms	10328 KiB

Main

#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<ll, ll>
typedef long long ll;
const ll MOD = 1000000007LL;
const ll INF = 1e15;
using namespace std;

ll n, a[200010], pre[200010], suf[200010];
ll ans1[200010], ans2[200010], ans;

int main() {
	cin.tie(0); cout.tie(0);
	ios::sync_with_stdio(0);
	
	cin >> n ;
	for (int i = 1; i <= n; i++) cin >> a[i];
	
	pre[1] = suf[n] = 0;
	for (int i = 2; i <= n; i++) pre[i] = max(0LL, pre[i-1]+a[i-1]+1-a[i]);
	for (int i = n-1; i >= 1; i--) suf[i] = max(0LL, suf[i+1]+a[i+1]+1-a[i]);
	
	ans1[1] = pre[1]; ans2[n] = suf[n];
	for (int i = 2; i <= n; i++) ans1[i] = ans1[i-1]+max(0LL, pre[i]-pre[i-1]);
	for (int i = n-1; i >= 1; i--) ans2[i] = ans2[i+1]+max(0LL, suf[i]-suf[i+1]);
	
//	for (int i = 1; i <= n; i++) cout << a[i] << ' ' << pre[i] << ' ' << suf[i] << ' ' << ans1[i] << ' ' << ans2[i] << "\n";
	
	ans = INF;
	for (int i = 1; i <= n; i++) {
		ans = min(ans, max(ans1[i], ans2[i]));
	}
	
	cout << ans << "\n";
	
	return 0;
}
/*



*/

• Subtask 1: 40 / 40
• Subtask 2: 60 / 60