Submission #433466

#	Time	Username	Problem	Language	Result	Execution time	Memory
433466		xuliu	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++14	0 / 100	1 ms	204 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define dbg if(0)

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	vector<ll> a(n), b(n), l(n, 0), r(n, 0);
	for(int i=0; i<n; i++)
		cin>>a[i];
	for(int i=0; i<(n-1); i++)
		b[i] = a[i+1] - a[i];
	for(int i=1; i<n; i++)
		l[i] = l[i-1] + max(0LL, 1-b[i-1]);
	for(int i=(n-2); i>=0; i--)
		r[i] = r[i+1] + max(0LL, b[i]+1);
	dbg {
		cerr<<"l: ";
		for(int i=0; i<n; i++)
			cerr<<l[i]<<" ";
		cerr<<"\nr: ";
		for(int i=0; i<n; i++)
			cerr<<r[i]<<" ";
		cerr<<"\n";
	}
	ll ans = max(l[0], r[0]);
	for(int i=2; i<n; i++)
		ans = min(ans, max(l[i], r[i]));
	cout<<ans;
}

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