This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// 23 - 12 - 23
#include<bits/stdc++.h>
using namespace std;
#define read() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define day() time_t now = time(0);char* x = ctime(&now);cerr<<"Right Now Is : "<<x<<"\n"
#define int long long
#define ii pair<int,int>
#define X first
#define Y second
const long long MAX = (int)2e5 + 5;
const long long INF = (int)1e9;
const long long MOD = (int)1e9 + 7;
int n,a[MAX];
int dp[MAX],b[MAX],f[MAX];
signed main(){
read();
cin >> n;
for(int i = 1;i <= n;i++){
cin >> a[i];
b[i] = a[i];
dp[i] = dp[i - 1];
if(i > 1){
if(b[i] <= b[i - 1]){
dp[i] += b[i - 1] + 1 - b[i];
}
}
}
for(int i = n;i >= 1;i--){
f[i] = f[i + 1];
if(i < n){
if(b[i] <= b[i + 1])f[i] += b[i + 1] + 1 - b[i];
}
}
int res = f[1];
for(int i = 2;i <= n;i++){
res = min(res,max(f[i],dp[i]));
}
cout << res;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |