Submission #1281775

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281775		Faisal_Saqib	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++20	0 / 100	2 ms	572 KiB

Main

#include <iostream>
using namespace std;
#define ll long long
const int N=2e5+10;
ll a[N],b[N];
int main()
{
    int n;
    cin>>n;
    ll mx=-100;
    // pair<ll,int> mx={-100,-100};
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        b[i]=a[i];
        mx=max(mx,a[i]);
    }
    ll ans=1e18;
    // for(int k=1;k<=n;k++)
    // int k=mx.second;
    for(int k=1;k<=n;k++)
    {
        if(b[k]!=mx)continue;
        for(int j=1;j<=n;j++)
        {
            a[j]=b[j];
        }
        ll cur=0;
        // cout<<"Left "<<endl;
        // for(int i=k-1;i>=1;i--)
        // {
        //     cout<<max(0ll,1+a[i]-a[i+1])<<' ';
        // }
        // cout<<endl;
        // cout<<"Right "<<endl;
        // for(int i=k+1;i<=n;i++)
        // {
        //     cout<<max(0ll,1+a[i]-a[i-1])<<' ';
        // }
        // cout<<endl;
        int i=k-1,j=k+1;

        while(1<=i and j<=n)
        {
            // a[j-1] <= a[j]
            // 0 < a[j]+1-a[j-1]
            // a[j]-a[j-1]
            // a[i]>a[i+1]
            ll inc_r=max(0ll,1+a[j]-a[j-1]);
            ll inc_l=max(0ll,1+a[i]-a[i+1]);
            if(inc_r<=inc_l)
            {
                cur+=inc_r;
                // cout<<"AddW1 "<<inc_r<<endl;
                a[j-1]+=inc_r;
                // cout<<"B "<<i+1<<' '<<a[i+1]<<endl;
                if((j-1)!=(i+1))
                    a[i+1]+=inc_r;
                // cout<<i+1<<' '<<a[i+1]<<endl;
                j++;
                // a[j-1]+inc_r >= a[j]
            }
            else
            {
                cur+=inc_l;
                // cout<<"AddW2 "<<inc_l<<endl;
                a[i+1]+=inc_l;
                if((j-1)!=(i+1))
                    a[j-1]+=inc_l;
                i--;
            }
        }
        while(1<=i)
        {
            // cout<<i<<' '<<a[i]<<' '<<a[i+1]<<endl;
            cur+=max(0ll,1+a[i]-a[i+1]);
            // cout<<"AddI "<<max(0ll,1+a[i]-a[i+1])<<endl;
            i--;
        }
        while(j<=n)
        {
            cur+=max(0ll,1+a[j]-a[j-1]);
            // cout<<"AddJ "<<max(0ll,1+a[j]-a[j-1])<<endl;
            j++;
        }
        // cout<<"Current: ";
        // cout<<cur<<' ';
        // cout<<endl<<endl;
        ans=min(ans,cur);
    }
    // cout<<endl;
    cout<<ans<<endl;
}
// 

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