Submission #936671

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

Main

#include<bits/stdc++.h>

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


vector<int> dp[2];

signed main(){
    int n;
    cin>>n;
    vector<int>v(n);
    for(int i = 0; i<n; i++){
        cin>>v[i];
    }

    for(int i = 0; i<2; i++){
        dp[i].resize(n);

        dp[i][0] = 0;
        for(int j = 1; j<n; j++){
            dp[i][j] = dp[i][j-1];
            if(v[j]<=v[j-1]){
                dp[i][j] += v[j-1]-v[j]+1;
            }
        }
        reverse(v.begin(), v.end());
    }
    reverse(dp[1].begin(), dp[1].end());

    int res= 1e18;
    for(int i = 0; i<n; i++){
        //cout<<dp[0][i]<<" "<<dp[1][i]<<endl;
        res = min(res, max(dp[0][i], dp[1][i]));
    }
    cout<<res<<endl;
}

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