이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
int n;
// int spar[200005][20];
// int pwr[20];
int a[200005];
// void init() {
// pwr[0] = 1;
// for (int i = 1; i < 20; i++) pwr[i] = pwr[i - 1] * 2;
// for (int i = 0; i < n; i++) spar[i][0] = i;
// for (int i = 1; i < 20; i++) {
// for (int j = 0; j < n; j++) {
// int nxt = j + pwr[i - 1];
// int dex1 = spar[j][i - 1];
// if (nxt >= n) {
// spar[j][i] = dex1;
// continue;
// }
// int dex2 = spar[nxt][i - 1];
// if (a[dex1] < a[dex2]) spar[j][i] = dex1;
// else spar[j][i] = dex2;
// }
// }
// }
// int get_min(int l, int r) {
// if (l == r) {
// return l;
// }
// int diff = r - l + 1;
// int lg2 = 0;
// while (pwr[lg2 + 1] <= diff) ++lg2;
// int dex1 = spar[l][lg2];
// int dex2 = spar[r - pwr[lg2] + 1][lg2];
// if (a[dex1] < a[dex2]) return dex1;
// else return dex2;
// }
int con1[200005];
int con2[200005];
int diff1[200005];
int diff2[200005];
int presum[200005];
int postsum[200005];
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) {
if (i == 0) con1[i] = 0;
else {
con1[i] = max(a[i - 1] + 1 - a[i], 0);
}
}
for (int i = n - 1; i >= 0; i--) {
if (i == n - 1) con2[i] = 0;
else {
con2[i] = max(a[i + 1] + 1 - a[i], 0);
}
}
// for (int i = 0; i < n; i++) {
// cout << "#" << i << " " << con1[i] << " " << con2[i] << endl;
// }
for (int i = 0; i < n; i++) {
if (i == 0) presum[i] = con1[i];
else presum[i] = presum[i - 1] + con1[i];
}
for (int i = n - 1; i >= 0; i--) {
if (i == n - 1) postsum[i] = con2[i];
else postsum[i] = postsum[i + 1] + con2[i];
}
// for (int i = 0; i < n; i++) {
// cout << "!" << i << " " << presum[i] << " " << postsum[i] << endl;
// }
int ans = 1e9;
for (int i = 0; i < n; i++) {
// int pre = s
// int x = max(con1[i], con2[i]);
ans = min(ans, max(presum[i], postsum[i]));
}
cout << ans << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |