Submission #814711

#	Time	Username	Problem	Language	Result	Execution time	Memory
814711		anton	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	70 ms	7084 KiB

Main

#include<bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int, int>


const int MAX_N = 2* 1e5;
int n, A[MAX_N];
int pref[MAX_N], suf[MAX_N];
signed main(){
    cin>>n;

    for(int i = 0; i<n; i++){
        cin>>A[i];
    }

    pref[0] = 0;

    for(int i = 1; i<n; i++){
        pref[i] =pref[i-1];
        if(A[i-1]>=A[i]){
            pref[i] += A[i-1]-A[i] + 1;
        }
    }
    suf[n-1] = 0;

    for(int i = n-2; i>=0; i--){
        suf[i] = suf[i+1];

        if(A[i] <= A[i+1]){
            suf[i] += A[i+1]-A[i]+1;
        }
    }

    int res = 1e18;

    for(int i = 0; i<n; i++){
        res = min(res, max(pref[i],suf[i]));
    }
    cout<<res<<endl;
}

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