/// 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 |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |