이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;cin>>n;
vector<long long>arr(n);
for (int i = 0;i<n;++i){
cin>>arr[i];
}
vector<long long>diff;
for (int i = 1;i<n;++i){
diff.push_back(arr[i - 1] - arr[i]);
}
vector<long long>pref(n + 1,0);
vector<long long>suff_max(n + 1,0),pref_max(n + 1,0);
pref[0] = 0;
for (int i = 0;i<n - 1;++i){
pref[i + 1] = pref[i] + max(0LL,diff[i] + 1);
pref_max[i + 1] = max(pref_max[i],max(0LL,diff[i] + 1));
}
vector<long long>suff(n + 1,0);
suff[n - 1] = 0;
for (int i = n - 1;i>=1;--i){
suff[i - 1] = suff[i] + max(0LL,-(diff[i - 1] - 1));
suff_max[i - 1] = max(suff_max[i],max(0LL,-(diff[i - 1] - 1)));
}
long long ans = 1e15;
for (int i = 0;i<n - 1;++i){
ans = min(ans,pref[i] + suff[i] - min(pref_max[i],suff_max[i]));
}
cout<<ans<<'\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |