Submission #756349

#	Time	Username	Problem	Language	Result	Execution time	Memory
756349		1075508020060209tc	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++14	100 / 100	116 ms	14796 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
int ans;
int oar[1000006];
int ar[1000006];
int par[1000006];
int sar[1000006];
int ps[1000006];
int sf[1000006];
int adp[200005];
int sfp[200005];
signed main(){
 
cin>>n;
for(int i=1;i<=n;i++){
    cin>>ar[i];
    oar[i]=ar[i];
    par[i]=ar[i];
    sar[i]=ar[i];
}
for(int i=2;i<=n;i++){
    ps[i]=ps[i-1];
    if(par[i]<=par[i-1]){
        par[i]=par[i-1]+1;
        ps[i]+=max(0ll,ar[i-1]-ar[i]+1);
        adp[i]=max(0ll,ar[i-1]-ar[i]+1);
    }
}
for(int i=n-1;i>=1;i--){
    sf[i]=sf[i+1];
    if(sar[i]<=sar[i+1]){
        sar[i]=sar[i+1]+1;
        sf[i]+=max(0ll,ar[i+1]-ar[i]+1);
        sfp[i]=max(0ll,ar[i+1]-ar[i]+1);
    }
}
 
 
for(int i=1;i<=n;i++){
    adp[i]=max(adp[i],adp[i-1]);
}
for(int i=n;i>=1;i--){
    sfp[i]=max(sfp[i+1],sfp[i]);
}
ans=min(ps[n],sf[1]);
for(int i=2;i<=n;i++){
    int cal=max(ps[i-1],sf[i]);
    if(par[i-1]==sar[i]){
        cal=max(ps[i-1]+1,sf[i]);
        cal=min(cal,max(ps[i-1],sf[i]+1));
    }
    ans=min(ans,cal);
}
 
 
 
 
 
cout<<ans<<endl;
 
}

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