This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define debug(x) cerr << #x << ' ' << x << '\n'
#define endl '\n'
#define printv(v) cerr << #v << ": "; for (auto& n: v) cerr << n << " \n"[&n==&v.back()]
using namespace std;
const int M = 1e9 + 7;
typedef long long ll;
int main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int N;
cin >> N;
vector<ll> v(N);
for (auto& n: v) cin >> n;
vector<ll> left(N), right(N), dpl(N), dpr(N);
ll goal;
dpl[0] = v[0];
dpr.back() = v.back();
for (int i = 1; i < N; i++) {
goal = dpl[i] = max(dpl[i - 1] + 1, v[i]);
left[i] = left[i - 1] + max(goal - v[i] - dpl[i - 1] + v[i - 1], 0LL);
}
for (int i = N - 2; i >= 0; i--) {
goal = dpr[i] = max(dpr[i + 1] + 1, v[i]);
right[i] = right[i + 1] + max(goal - v[i] - dpr[i + 1] + v[i + 1], 0LL);
}
//printv(left);
//printv(dpl);
//printv(right);
//printv(dpr);
ll ans = INT64_MAX;
for (int i = 0; i < N; i++) {
ans = min(left[i] + right[i] - min(dpl[i], dpr[i]) + v[i], ans);
}
cerr << "answer: ";
cout << ans << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |