이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e9 + 5;
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
vector<int> A(N + 2);
A[0] = A[N + 1] = 0;
for (int i = 1; i <= N; i++)
cin >> A[i];
vector<int> B(A);
vector<int> pref(N + 2, 0), suf(N + 2, 0);
for (int i = 1, j = N; i <= N; i++, j--) {
pref[i] = pref[i - 1];
suf[j] = suf[j + 1];
A[i] += pref[i];
B[j] += suf[j];
if (A[i] <= A[i - 1]) {
pref[i] += A[i - 1] - A[i] + 1;
A[i] = A[i - 1] + 1;
}
if (B[j] <= B[j + 1]) {
suf[j] += B[j + 1] - B[j] + 1;
B[j] = B[j + 1] + 1;
}
}
int ans = INF;
for (int i = 1; i <= N; i++) {
int mx = max(pref[i], suf[i + 1]);
// cout << i << " " << mx << "\n";
// cout << A[i] << " " << B[i + 1] << "\n\n";
ans = min(ans, mx + (A[i] == B[i + 1] ? A[i] == B[i + 1] : 0));
}
cout << ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |