Submission #378319

#	Time	Username	Problem	Language	Result	Execution time	Memory
378319		astoria	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++14	100 / 100	218 ms	14572 KiB

Main

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

#define int long long

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int n; cin>>n;
	int a[n+5],b[n+5],d[n+5];
	for(int i=1; i<=n; i++) cin>>a[i];
	multiset<int> diff;
	b[n] = a[n]; diff.insert(0); d[n]=0;
	for(int i=n-1; i>0; i--){
		b[i]=max({a[i],b[i+1]+1,a[i]+d[i+1]});
		d[i]=b[i]-a[i];
		//b[i]=max(a[i],b[i+1]+1);
		diff.insert(d[i]);
	}
	b[n+1]=a[n+1]=a[n]-1; b[0]=a[0]=a[1]-1; d[0]=0; d[n+1]=0;
	int an = *diff.rbegin();
	
	//cout<<an<<endl;
	//for(int i : diff) cout<<i<<' ';
	
	//cout<<"HEY"<<endl;
	for(int i=2; i<=n; i++){
		//cout<<(*diff.rbegin())<<endl;
		//shift peak
		int prev = b[i-1]-a[i-1], cr = b[i]-a[i];
		
		b[i-1] = max({a[i-1],b[i-2]+1,a[i-1]+d[i-2]});
		/*if(i==5){
			cout<<b[i-1]<<' '<<a[i-1]<<' '<<b[i-2]<<' '<<d[i-2]<<"P"<<endl;
		}*/
		
		d[i-1]=b[i-1]-a[i-1];
		b[i] = max({a[i],b[i-1]+1,b[i+1]+1,a[i]+min(d[i-1],d[i+1])});
		//b[i-1]=max(a[i-1],b[i-2]+1);
		//b[i]=max({a[i],b[i-1]+1,b[i+1]+1});
		diff.erase(diff.find(prev));
		diff.erase(diff.find(cr));
		d[i-1]=b[i-1]-a[i-1]; d[i]=b[i]-a[i];
		diff.insert(d[i-1]);
		diff.insert(d[i]);
		an=min(an, *diff.rbegin());
	}
	cout<<an;
}

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