제출 #1230489

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1230489		harryleee	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++20	100 / 100	15 ms	8264 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int n;
long long a[maxn], inc_time[maxn], dec_time[maxn], inc_val[maxn], dec_val[maxn];
long long res = 1e18;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    inc_time[1] = 0;
    inc_val[1] = 0;
    for (int i = 2; i <= n; ++i) {
        inc_time[i] = max(0LL, inc_time[i-1] + a[i-1] + 1 - a[i]);
        inc_val[i] = inc_val[i-1] + max(0LL, inc_time[i] - inc_time[i-1]);
    }

    dec_time[n] = 0;
    dec_val[n] = 0;
    for (int i = n-1; i >= 1; --i) {
        dec_time[i] = max(0LL, dec_time[i+1] + a[i+1] + 1 - a[i]);
        if (i == n-1) 
            dec_val[i] = max(0LL, dec_time[i] - dec_time[i+1]);
        else 
            dec_val[i] = dec_val[i+1] + max(0LL, dec_time[i] - dec_time[i+1]);
    }

    for (int k = 1; k <= n; ++k) {
        long long ops = max(inc_val[k], dec_val[k]);
        res = min(res, ops);
    }

    cout << res;
    return 0;
}

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