This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define ff first
#define ss second
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#define ins insert
#define endl "\n"
#define flush fflush(stdout)
#define deb(x) cout<<(x)<<endl
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x<<" "<<x<<endl
const ll INF=1e17,MOD=1e9+7,MAXN=3e5+5;
ll A[MAXN],pref[MAXN],suff[MAXN],add[MAXN];
int tt=1,n;
void solve(){
add[0] = 0;
cin>>n; A[0] = A[n+1] = -INF; pref[0] = suff[n+1] = 0;
for(int i=1;i<=n;i++) {
cin>>A[i];
pref[i] = pref[i-1] + max(0ll,A[i-1] - A[i] + 1);
add[i] = add[i-1] + max(0ll,A[i-1] - A[i] + 1);
}
for(int i=n;i>=1;i--) {
suff[i] = suff[i+1] + max(0ll,A[i+1] - A[i] + 1);
}
ll mn = INF;
for(int i=1;i<=n;i++) {
ll tmp = pref[i] + suff[i] - min(suff[i],add[i]);
mn = min(mn,tmp);
} deb(mn);
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
// cin>>tt;
while(tt--){
solve();
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |