제출 #1186208

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

Main

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

int n;
ll a[200005], vall[200005], valr[200005];
ll difl[200005], difr[200005];
ll qsl[200005], qsr[200005];
ll ans = LLONG_MAX;

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=n;i++) vall[i] = max(vall[i-1] + 1, a[i]);
    for(int i=n;i>=1;i--) valr[i] = max(valr[i+1] + 1, a[i]);
    for(int i=1;i<=n;i++) {
        difl[i] = vall[i] - a[i];
        qsl[i] = qsl[i-1] + max(0ll, difl[i]-difl[i-1]);
    }
    for(int i=n;i>=1;i--) {
        difr[i] = valr[i] - a[i];
        qsr[i] = qsr[i+1] + max(0ll, difr[i]-difr[i+1]);
    }
    ans = min(qsl[n], qsr[1]);
    for(int i=2;i<=n;i++) {
        ans = min(ans, max(qsl[i-1], qsr[i]) + (vall[i-1] == valr[i]));
    }
    cout << ans;    
}

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