Submission #1186141

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186141		peteza	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++20	0 / 100	1 ms	328 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int n, arr[200005];
int vall[200005], valr[200005];
ll qsl[200005], qsr[200005];
ll ans = LLONG_MAX;
 
int main() {
	cin.tie(0) -> sync_with_stdio(0);
	cin >> n;
	for(int i=1;i<=n;i++) cin >> arr[i];
	for(int i=1;i<=n;i++) {
		vall[i] = max(vall[i-1]+1, arr[i]);
		qsl[i] = qsl[i-1] + (vall[i] - arr[i]);
	}
	for(int i=n;i>=1;i--) {
		valr[i] = max(valr[i+1]+1, arr[i]);
		qsr[i] = qsr[i+1] + (valr[i] - arr[i]);
	}
	ans = min(qsl[n], qsr[1]);
	for(int i=2;i<=n;i++) {
		ans = min(ans, max(qsl[i-1], qsr[i]) + (vall[i-1] == valr[i]));
	}
	cout << ans;
}

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