Submission #555832

#	Time	Username	Problem	Language	Result	Execution time	Memory
555832		alextodoran	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	40 ms	6168 KiB

Main

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 200000;

int N;
int A[N_MAX + 2];

ll L[N_MAX + 2];
ll R[N_MAX + 2];

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> A[i];
    }
    for (int i = 1; i <= N; i++) {
        L[i] = L[i - 1] + max(0, A[i - 1] - A[i] + 1);
    }
    for (int i = N; i >= 1; i--) {
        R[i] = R[i + 1] + max(0, A[i + 1] - A[i] + 1);
    }
    ll answer = LLONG_MAX;
    for (int i = 1; i <= N; i++) {
        answer = min(answer, max(L[i], R[i]));
    }
    cout << answer << "\n";

    return 0;
}

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