Submission #411667

#	Time	Username	Problem	Language	Result	Execution time	Memory
411667		dolijan	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++14	100 / 100	119 ms	8488 KiB

Main

#include <bits/stdc++.h>
typedef long long ll ;
using namespace std;
const ll mn=2*1e5+100;
const ll  INF=1e18;
ll a[mn];
ll diff[mn];
ll pref[mn];
ll suf[mn];
int main()
{
    ll n;
    cin>>n;
    for(ll i=0;i<n;i++) cin>>a[i];
    for(ll i=1;i<n;i++) diff[i-1]=a[i-1]-a[i];
    n--;
    pref[0]=max(0LL,diff[0]+1);
    for(ll i=1;i<n;i++) pref[i]=pref[i-1]+max(0LL,diff[i]+1);
    suf[n-1]=max(0LL,1-diff[n-1]);
    for(ll i=n-2;i>=0;i--) suf[i]=suf[i+1]+max(0LL,1LL-diff[i]);
    ll mn=INF;
    for(ll i=0;i<n-1;i++) mn=min(max(pref[i],suf[i+1]),mn);
    //cout<<mn<<endl;
    mn=min(min(suf[0],pref[n-1]),mn);
    cout<<mn<<endl;
}

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