Submission #1281736

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281736		Faisal_Saqib	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++20	40 / 100	1096 ms	3476 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;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        b[i]=a[i];
    }
    ll ans=1e18;
    for(int k=1;k<=n;k++)
    {
        for(int j=1;j<=n;j++)
        {
            a[j]=b[j];
        }
        ll cur=0;
        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;
                a[j-1]+=inc_r;
                a[i+1]+=inc_r;
                j++;
                // a[j-1]+inc_r >= a[j]
            }
            else
            {
                cur+=inc_l;
                a[j-1]+=inc_l;
                a[i+1]+=inc_l;
                i--;
            }
        }
        while(1<=i)
        {
            cur+=max(0ll,1+a[i]-a[i+1]);
            i--;
        }
        while(j<=n)
        {
            cur+=max(0ll,1+a[j]-a[j-1]);
            j++;
        }
        ans=min(ans,cur);
    }
    cout<<ans<<endl;
}

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