Submission #649891

#	Time	Username	Problem	Language	Result	Execution time	Memory
649891		ivaziva	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++14	100 / 100	87 ms	8604 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define MAXN 200010
#define A -1000000000

long long n;
long long niz[MAXN];
long long p[MAXN];
long long prefix[MAXN];
long long sufix[MAXN];

int main()
{
    cin>>n;

    niz[0]=niz[n+1]=A;
    for (long long i=1;i<=n;i++) cin>>niz[i];

    for (long long i=1;i<=n+1;i++) p[i]=niz[i]-niz[i-1];

    for (long long i=1;i<=n;i++)
    {
        prefix[i]=prefix[i-1];
        if (p[i]<=0) prefix[i]+=(1-p[i]);
    }

    for (long long i=n;i>=1;i--)
    {
        sufix[i]=sufix[i+1];
        if (p[i]>=0) sufix[i]+=p[i]+1;
    }

    long long maksi=max(prefix[1],sufix[2]);

    for (long long i=2;i<=n;i++) maksi=min(maksi,max(prefix[i],sufix[i+1]));

    cout<<maksi<<endl;
}

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