Submission #425317

#	Time	Username	Problem	Language	Result	Execution time	Memory
425317		jovan_b	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	39 ms	10116 KiB

Main

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int MAXN = 200000;

ll a[MAXN+5];
ll pref[MAXN+5];
ll suf[MAXN+5];
ll hpref[MAXN+5];
ll hsuf[MAXN+5];

const ll INF = 1000000000000000000LL;

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n;
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    for(int i=1; i<=n; i++){
        hpref[i] = max(hpref[i-1] + 1, a[i] + pref[i-1]);
        pref[i] = pref[i-1] + max(0LL, hpref[i] - (a[i] + pref[i-1]));
    }
    for(int i=n; i>=1; i--){
        hsuf[i] = max(hsuf[i+1] + 1, a[i] + suf[i+1]);
        suf[i] = suf[i+1] + max(0LL, hsuf[i] - (a[i] + suf[i+1]));
    }
    ll res = INF;
    for(int i=1; i<=n; i++){
        res = min(res, max(pref[i-1], max(suf[i+1], max(hpref[i-1], hsuf[i+1]) + 1 - a[i])));
    }
    cout << res << "\n";
    return 0;
}

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