Submission #649550

#	Time	Username	Problem	Language	Result	Execution time	Memory
649550		sofija6	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++14	100 / 100	33 ms	8524 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define MAXN 200010
#define llinf 1000000000000
using namespace std;
ll a[MAXN],p[MAXN],neg[MAXN],pos[MAXN];
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,ans=LLONG_MAX;
    cin >> n;
    a[0]=-llinf;
    a[n+1]=llinf;
    for (ll i=1;i<=n;i++)
        cin >> a[i];
    for (ll i=1;i<=n+1;i++)
        p[i]=a[i]-a[i-1];
    for (ll i=2;i<=n;i++)
    {
        pos[i]=pos[i-1]+(p[i]>0?0 : abs(p[i])+1);
        neg[i]=neg[i-1]+(p[i]<0?0 : p[i]+1);
    }
    for (ll i=1;i<=n;i++)
        ans=min(ans,max(pos[i],neg[n]-neg[i]));
    cout << ans;
    return 0;
}

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