| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1162959 | DEQK | Growing Vegetables is Fun 4 (JOI21_ho_t1) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define pb push_back
#define F first
#define S second
#define sz(a) ((int) a.size())
const int N = 3e5 + 15;
int n, a[N];
pair<pair<int, ll>, ll> pref[N], suf[N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
pref[1] = {{a[1], 0}, 0};
for(int i = 2; i <= n; i++) {
int x = pref[i - 1].F.F;
int lst = pref[i - 1].F.S;
ll cnt = pref[i - 1].S;
if(a[i] + cnt > x) {
pref[i] = {{a[i] + cnt, lst}, cnt};
} else {
int op = x + 1 - (a[i] + cnt);
pref[i] = {{x + 1, lst + op}, cnt + op};
}
}
suf[n] = {{a[n], 0}, 0};
for(int i = n - 1; i >= 1; i--) {
int x = suf[i + 1].F.F;
int lst = suf[i + 1].F.S;
ll cnt = suf[i + 1].S;
if(a[i] + cnt > x) {
suf[i] = {{a[i] + cnt, lst}, cnt};
} else {
int op = x + 1 - (a[i] + cnt);
suf[i] = {{x + 1, lst + op}, cnt + op};
}
}
// cout << "3 pref = {" << pref[3].F.F << ' ' << pref[3].F.S << ' ' << pref[3].S << " }" << '\n';
// cout << "3 suf = {" << suf[3].F.F << ' ' << suf[3].F.S << ' ' << suf[3].S << " }" << '\n';
// return 0;
ll ans = min(pref[n].S, suf[1].S);
for(int i = 2; i < n; i++) {
//cout << i << " = " << pref[i].S + suf[i].S - min(pref[i].F.S, suf[i].F.S) << ' ';
ans = min(ans, max(pref[i].S, suf[i].S));
}
cout << ans << '\n';
}