Submission #994505

#	Time	Username	Problem	Language	Result	Execution time	Memory
994505		mnieplowicz	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	21 ms	8676 KiB

Main

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

int tab[200005];
int R[200005];
int pref[200005];
int suf[200005];

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> tab[i];
		R[i] = tab[i] - tab[i-1];
	}
	for(int i = 2; i <= n; i++){
		pref[i] = pref[i-1];
		if(R[i] <= 0) pref[i] += (-R[i])+1;
	}
	for(int i = n-1; i > 0; i--){
		suf[i] = suf[i+1];
		if(R[i+1] >= 0) suf[i] += R[i+1]+1;
	}
	int res = 1e18;
	for(int i = 1; i <= n; i++){
		 res = min(res, max(suf[i], pref[i]));
	}
	cout << res << '\n';
	return 0;
}

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