Submission #830417

#	Time	Username	Problem	Language	Result	Execution time	Memory
830417		RaresFelix	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	70 ms	6984 KiB

Main

#include <bits/stdc++.h>

using namespace std;
const int MN = 200071;
using ll = long long;
ll n, A[MN], St[MN], Dr[MN];
int main() {
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        cin >> A[i];
    }
    for(int i = n; i >= 1; --i) A[i] -= A[i - 1];
    for(int i = 1; i < n; ++i) A[i] = A[i + 1];
    --n;
    ll s = 0;
    for(int i = 1; i <= n; ++i) {
        s += max(1 - A[i], 0ll);
        St[i] = s; 
    }
    s = 0;
    for(int i = n; i >= 1; --i) {
        s += max(A[i] + 1, 0ll);
        Dr[i] = s;
    }
    ll re = min(St[n], Dr[1]);
    for(int i = 1; i <= n; ++i) {
        re = min(re, max(St[i], Dr[i + 1]));
    }
    cout << re << "\n";

    return 0;
}

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