Submission #761789

#	Time	Username	Problem	Language	Result	Execution time	Memory
761789		nihon	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++14	100 / 100	66 ms	8300 KiB

Main

#include <bits/stdc++.h>
#define N 200005
using namespace std;
long long n,i,a[N],v[N],w[N],p[N],s[N],mn=2e18;
int main()
{
    cin>>n;
    for(i=1;i<=n;++i)
    {
        cin>>a[i];
    }
    for(i=1;i<=n;++i)
    {
        if(i==1){v[i]=0; continue;}
        if(a[i]>(a[i-1]+v[i-1]))
        {
            v[i]=0;
        }
        else
        {
            v[i]=(a[i-1]+v[i-1])-a[i]+1;
        }
    }
    for(i=n;i>=1;--i)
    {
        if(i==n){w[i]=0; continue;}
        if(a[i]>(a[i+1]+w[i+1]))
        {
            w[i]=0;
        }
        else
        {
            w[i]=(a[i+1]+w[i+1])-a[i]+1;
        }
    }
    for(i=1;i<=n;++i)
    {
        if(i==1){p[i]=0; continue;}
        if(v[i]>v[i-1]) p[i]=p[i-1]+(v[i]-v[i-1]);
        else p[i]=p[i-1];
    }
    for(i=n;i>=1;--i)
    {
        if(i==n){s[i]=0; continue;}
        if(w[i]>w[i+1]) s[i]=s[i+1]+(w[i]-w[i+1]);
        else s[i]=s[i+1];
    }
    for(i=1;i<=n;++i)
    {
        mn=min(mn,max(p[i],s[i]));
    }
    cout<<mn;
    return 0;
}

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