이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 200010;
int addpref[N], addsuf[N];
int nump[N], nums[N];
int v[N];
int32_t main(){
int n;
cin >> n;
for(int i = 1;i <= n;i++)
cin >> v[i];
nump[1] = v[1];
for(int i = 2;i <= n;i++){
nump[i] = max(nump[i-1]+1, v[i]);
}
nums[n] = v[n];
for(int i = n-1;i >= 1;i--){
nums[i] = max(nums[i+1]+1, v[i]);
}
for(int i = 1;i <= n;i++){
addpref[i] = nump[i] - v[i];
addsuf[i] = nums[i] - v[i];
}
int pref[N], suf[N];
pref[1] = 0;
int ant = 0;
for(int i = 2;i <= n;i++){
pref[i] = pref[i-1];
if(ant < addpref[i]) pref[i] += addpref[i] - ant;
ant = addpref[i];
}
ant = 0;
for(int i = n-1;i > 0;i--){
suf[i] = suf[i+1];
if(ant < addsuf[i]) suf[i] += addsuf[i] - ant;
ant = addsuf[i];
}
int res = 1e18;
for(int i = 1;i <= n;i++){
if(addpref[i] == addsuf[i]) res = min(res, min(max(pref[i], suf[i+1]), max(pref[i-1], suf[i])));
res = min(res, (addpref[i] > addsuf[i] ? max(pref[i], suf[i+1]) : max(pref[i-1], suf[i])));
}
cout << res << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |