Submission #530294

#	Time	Username	Problem	Language	Result	Execution time	Memory
530294		Darren0724	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	0 / 100	24 ms	204 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
int INF=1e18;
vector<int> v;
int ans=INF;
int n;
void sol(int k){
    vector<int> p(n);
    p[0]=v[0];
    p[n-1]=v[n-1];
    for(int i=1;i<=k;i++){
        p[i]=max(p[i-1]+1,v[i]);
    }
    for(int i=n-2;i>=k;i--){
        p[i]=max({p[i+1]+1,v[i],p[i]});
    }
    int cnt=0;
    for(int i=0;i<n;i++){
        p[i]=p[i]-v[i];
        //cout<<p[i]<<' ';
    }
    //cout<<endl;
    int rec=0;
    for(int i=0;i<n;i++){
        if(i==k){
            if(k!=0){
                p[i]=max(p[i-1],p[i]);
            }
            if(k!=n-1){
                p[i]=max(p[i],p[i+1]);
            }
        }
        cnt+=max((int)0,p[i]-rec);
        rec=p[i];
    }
    ans=min(ans,cnt);
    //cout<<k<<':'<<cnt<<endl;
}

signed main(){
    cin>>n;
    v.resize(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    for(int i=0;i<n;i++){
        sol(i);
    }
    cout<<ans<<endl;


}

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