Submission #505152

#	Time	Username	Problem	Language	Result	Execution time	Memory
505152		thomas_li	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	0 / 100	1 ms	332 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int MM = 2e5+5;
int n,a[MM],pref[MM],suff[MM];
int 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(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: 0 / 40
• Subtask 2: 0 / 60