Submission #531537

#	Time	Username	Problem	Language	Result	Execution time	Memory
531537		amunduzbaev	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	29 ms	10060 KiB

Main

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

#define ar array
#define int long long

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	vector<int> a(n), pref(n), pc(n);
	vector<int> suff(n), sc(n);
	for(int i=0;i<n;i++) cin>>a[i];	
	int v = a[0], add = 0;
	for(int i=1;i<n;i++){
		pref[i] = pref[i-1];
		if(a[i] > v){
			add = 0;
		} else {
			if(add < v + 1 - a[i]){
				pref[i] += ((v + 1) - a[i] - add);
			} add = v + 1 - a[i];
		}
		v = max(v + 1, a[i]);
		pc[i] = add;
	}
	
	v = a[n-1], add = 0;
	for(int i=n-2;~i;i--){
		suff[i] = suff[i+1];
		if(a[i] > v){
			add = 0;
		} else {
			if(add < v + 1 - a[i]){
				suff[i] += ((v + 1) - a[i] - add);
			} add = v + 1 - a[i];
		}
		v = max(v + 1, a[i]);
		sc[i] = add;
	}
	
	int res = 1e18;
	for(int i=0;i<n;i++){
		res = min(res, max(pref[i], suff[i]));
		//~ res = min(res, pref[i] + suff[i] - min(pc[i], sc[i]));
	}
	
	//~ for(int i=0;i<n;i++){
		//~ cout<<pref[i]<<" ";
	//~ } cout<<"\n";
	//~ for(int i=0;i<n;i++){
		//~ cout<<suff[i]<<" ";
	//~ } cout<<"\n";
	//~ for(int i=0;i<n;i++){
		//~ cout<<pc[i]<<" ";
	//~ } cout<<"\n";
	//~ for(int i=0;i<n;i++){
		//~ cout<<sc[i]<<" ";
	//~ } cout<<"\n";
	
	cout<<res<<"\n";
}

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