Submission #679956

#	Time	Username	Problem	Language	Result	Execution time	Memory
679956		redstonegamer22	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	91 ms	6888 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long

int32_t main() {
    int n; cin >> n;
    vector<int> a(n); for(auto &e : a) cin >> e;

    vector<int> dpl(n), dpr(n);

    for(int i = 0; i < n; i++) {
        if(i == 0) dpl[i] = 0;
        else {
            if(a[i] > a[i - 1]) dpl[i] = dpl[i - 1];
            else dpl[i] = dpl[i - 1] + (a[i - 1] + 1 - a[i]);
        }
    }

    for(int i = n - 1; i >= 0; i--) {
        if(i == n - 1) dpr[i] = 0;
        else {
            if(a[i] > a[i + 1]) dpr[i] = dpr[i + 1];
            else dpr[i] = dpr[i + 1] + (a[i + 1] + 1 - a[i]);
        }
    }

    int ans = (1LL << 50);
    for(int i = 0; i < n; i++) {
        ans = min(ans, max(dpl[i], dpr[i]));
    }

    cout << ans << endl;
}

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