Submission #1055253

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055253		fryingduc	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	20 ms	12508 KiB

Main

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

const int maxn = 2e5 + 5;
int n, a[maxn];
long long f[maxn], g[maxn];
long long pref[maxn], suf[maxn];
long long b[maxn], c[maxn];

void solve() {
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    for(int i = 1; i <= n; ++i) {
        pref[i] = max(pref[i - 1] + 1, 1ll * a[i]);
        b[i] = max(0ll, pref[i] - a[i]);
        f[i] = f[i - 1] + max(0ll, b[i] - b[i - 1]);
    }
    for(int i = n; i; --i) {
        suf[i] = max(suf[i + 1] + 1, 1ll * a[i]);
        c[i] = max(0ll, suf[i] - a[i]);
        g[i] = g[i + 1] + max(0ll, c[i] - c[i + 1]);
    }
    
    long long ans = min(f[n], g[1]);
    for(int i = 1; i < n; ++i) {
        ans = min(ans, max(f[i], g[i]));
    }
    
    cout << ans;
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    solve();
    return 0;
}

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