Submission #745286

#	Time	Username	Problem	Language	Result	Execution time	Memory
745286		IDorando	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	82 ms	6252 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int n, a[200005];
long long pref[200005], suff[200005], sol;

int main()
{
    int i;
    cin >> n;
    for (i = 1; i <= n; i++)
        cin >> a[i];

    pref[1] = 0;
    for (i = 2; i <= n; i++)
        if (a[i] <= a[i - 1])
            pref[i] = pref[i - 1] + a[i - 1] - a[i] + 1;
        else 
            pref[i] = pref[i - 1];

    suff[n] = 0;
    for (i = n - 1; i >= 1; i--)
        if (a[i] <= a[i + 1])
            suff[i] = suff[i + 1] + a[i + 1] - a[i] + 1;
        else
            suff[i] = suff[i + 1];

    sol = max(suff[1], pref[1]);
    for (i = 2; i <= n; i++)
        sol = min(sol, max(pref[i] , suff[i]));
    cout << sol;

    return 0;
}

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