This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/// 2021 A
#include <bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
int arr[200005];
//void db(){
// cout << "\n";
//}
//template<class T, class ...U>
//void db(T a, U ...b){
// cout << a << " "; db(b...);
//}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n, i;
cin >> n;
for (i=1; i<=n; i++)
cin >> arr[i];
if(n == 2){
if(arr[1] == arr[2]) cout << "1\n";
else cout << "0\n";
return 0;
}
for(int i = n; i >= 1; i--){
arr[i] = arr[i-1];
}
arr[1] = 0;
arr[n+1] = 0;
int l = 1, r = n;
int cnt = 0;
while (l + 2 <= r) {
//db(l, r);
if(arr[l] >= arr[l+1]){
cnt++;
arr[l+1]++;
arr[r-1]++;
}
else{
while(l + 2 <= r && arr[l] < arr[l+1]){
l++;
arr[l+1] += cnt;
}
if(l + 1 == r) break;
}
if(arr[r] >= arr[r-1]){
cnt++;
arr[l-1]++;
arr[r-1]++;
}
else{
while(l + 2 <= r && arr[r-1] < arr[r]){
r--;
arr[r-1] += cnt;
}
if(l + 1 == r) break;
}
}
cout << cnt << endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |