Submission #1281730

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281730		Faisal_Saqib	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++20	0 / 100	16 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;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        // a[i]-=i;
    }
    ll ans=1e18;
    for(int k=1;k<=n;k++)
    {
        ll ad=0;
        for(int i=1;i<=k;i++)
        {
            a[i]-=i;
        }
        for(int i=2;i<=k;i++)
        {
            ad+=max(0ll,a[i-1]-a[i]);
        }
        // a[k] ---> a[k]+ad
        for(int i=1;i<=k;i++)
        {
            a[i]+=i;
        }
        // a[k]+=ad;
        for(int i=k;i<=n;i++)
        {
            a[i]+=i;
        }
        a[k]+=ad;
        int p=k;
        for(int i=k+1;i<=n;i++)
        {
            if(a[i-1]>=(a[i]+ad))
            {
                p=i;
                a[i]+=ad;
            }
            else
            {
                break;
            }
        }
        ll xd=0;
        for(int i=n-1;i>=k;i--)
        {
            xd+=max(0ll,a[i+1]-a[i]);
        }
        for(int i=k;i<=n;i++)
        {
            a[i]-=i;
        }
        for(int i=k;i<=p;i++)a[i]-=ad;
        // a[k]-=ad;
        // cout<<"At "<<k<<" "<<xd+ad<<endl;
        ans=min(xd+ad,ans);
        // a[k]+ad   a[k]+xd
        // we make a[k]
    }
    for(int k=1;k<=n;k++)
    {
        for(int i=k;i<=n;i++)
        {
            a[i]+=i;
        }
        ll xd=0;
        for(int i=n-1;i>=k;i--)
        {
            xd+=max(0ll,a[i+1]-a[i]);
        }
        for(int i=k;i<=n;i++)
        {
            a[i]-=i;
        }
        a[k]+=xd;
        int p=k;
        for(int i=k-1;i>=1;i--)
        {
            if(a[i+1]>=a[i])
            {
                p=i;
                a[i]+=xd;
            }
            else
            {
                break;
            }
        }
        ll ad=0;
        for(int i=1;i<=k;i++)
        {
            a[i]-=i;
        }
        for(int i=2;i<=k;i++)
        {
            ad+=max(0ll,a[i-1]-a[i]);
        }
        // a[k] ---> a[k]+ad
        for(int i=1;i<=k;i++)
        {
            a[i]+=i;
        }
        for(int i=k;i>=p;i--)
        {
            a[i]-=xd;
        }
        // cout<<"At "<<k<<" "<<xd+ad<<endl;
        ans=min(xd+ad,ans);
        // a[k]+ad   a[k]+xd
        // we make a[k]
    }
    cout<<ans<<endl;
}

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