Submission #505156

#	Time	Username	Problem	Language	Result	Execution time	Memory
505156		thomas_li	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	28 ms	6940 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int int64_t
const int MM = 2e5+5;
int n,a[MM],pref[MM],suff[MM];
signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	int add = 0;
	for(int i = 1; i <= n; i++){
		if(i > 1 && a[i]+add <= a[i-1]+add){
			add += a[i-1]+add+1 - (a[i]+add);
		}
		pref[i] = add;
	}
	add = 0;
	for(int i = n; i >= 1; i--){
		if(i < n && a[i]+add <= a[i+1]+add){
			add += a[i+1]+add+1 - (a[i]+add);
		}
		suff[i] = add;
	}
	/*
	for(int i = 1; i <= n; i++){
		cout << pref[i] << " " << suff[i] << "\n";
	}*/
	int ans = min(suff[1],pref[n]);
	for(int i = 2; i < n; i++){
		int mx = max(suff[i+1],pref[i-1]);
		int v = a[i] + mx;
		int mxv = max(a[i-1]+pref[i-1],a[i+1]+suff[i+1]);
		int off = max(int64_t(0),(mxv+1) - v);
		ans = min(ans,mx + off);
	}
	cout << ans << "\n";
}
// claim: we should only do operations that cross k
// proof: magic
// thus, we can consider left and right seperately, and the answer would be max (lans,rans)

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