제출 #1186187

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1186187		peteza	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++20	0 / 100	1 ms	580 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] + difl[i];
    }
    for(int i=n;i>=1;i--) {
        difr[i] = valr[i] - a[i];
        qsr[i] = qsr[i+1] + difr[i];
    }
    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: 0 / 40
• Subtask 2: 0 / 60