Submission #406463

#	Time	Username	Problem	Language	Result	Execution time	Memory
406463		gromperen	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++14	100 / 100	37 ms	6980 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long


int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	ll n; cin >> n;
	vector<ll> a(n);
	for (int i = 0; i < n; ++i) cin >> a[i];

	vector <ll> pre(n,0), suf(n,0);
	for (int i = 1; i < n; ++i) {
		pre[i] = pre[i-1] + max(0LL, a[i-1] - a[i]+1);
		//cout << pre[i] << " ";
	}
	//cout << endl;
//
	for (int i = n - 2; i >= 0; --i) {
		suf[i] = suf[i+1] + max(0LL, a[i+1] - a[i] + 1);
		//cout << suf[i] << " ";
	}
	//cout << endl;

	ll ans = LLONG_MAX;
	for (int k = 0; k < n; ++k) {
		ans = min(ans, max(pre[k], suf[k]));
	}

	cout<< ans << endl;

	return 0;
}

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