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>
#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define sc second
#define endl "\n"
#define pii pair<int,int>
using namespace std;
const int MAXN = 1e5+5;
const int mod7 = 1e9+7;
const long long inf = 1e18;
signed main()
{
ios_base::sync_with_stdio(false),cin.tie(0), cout.tie(0);
int tt=1;
//cin >> tt;
while(tt--)
{
int n;
cin >> n;
vector<int> niz(n);
for(int i=0; i<n; i++)cin >> niz[i];
vector<int>pref(n,0);
vector<int>suf(n,0);
for(int i=0; i<n-1; i++)
{
pref[i+1] = pref[i];
if(niz[i] >= niz[i+1])pref[i+1]+= (niz[i] - niz[i+1]+1);
}
for(int i=n-2; i>=0; i--)
{
suf[i] = suf[i+1];
if(niz[i+1] >= niz[i])suf[i]+= (niz[i+1] - niz[i]+1);
}
int rez = inf;
//for(auto x: pref)cout << x << " ";cout << endl;
//for(auto x: suf)cout << x << " ";cout << endl;
for(int i=0; i<n; i++)
{
rez = min(rez, max(pref[i], suf[i]));
}
cout << rez << endl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |