Submission #575449

#	Time	Username	Problem	Language	Result	Execution time	Memory
575449		pokmui9909	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	31 ms	6960 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll N;
ll A[200005];
ll D[200005], E[200005];

int main(){
    cin.tie(0) -> sync_with_stdio(false);

    cin >> N;
    for(ll i = 1; i <= N; i++){
        cin >> A[i];
    }
    for(ll i = 2; i <= N; i++){
        D[i] = D[i - 1] + max(0LL, A[i - 1] + 1 - A[i]);
    }
    for(ll i = N - 1; i >= 1; i--){
        E[i] = E[i + 1] + max(0LL, A[i + 1] + 1 - A[i]);
    }
    ll r = 1e18;
    for(ll i = 1; i < N; i++){
        r = min(r, max(D[i], E[i + 1]) + (A[i] + D[i] == A[i + 1] + E[i + 1]));
    }
    cout << r;
}

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