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;
#define int long long
main(){
int n; cin >> n;
int arr[n]; for (int x = 0; x < n; x++) cin >> arr[x];
int ans = INT_MAX;
for (int k = 0; k < n; k++){
//try every point as the breaking point (max value)
int left = k, right = k;
int leftval = arr[k], rightval = arr[k];
int inc = 0;
while (left != 0 || right != n-1){
if (left != 0 && arr[left-1] - leftval < arr[right+1] - rightval){
if (arr[left-1] < leftval){
leftval = arr[left-1]; left--;
}
else{
inc += arr[left-1] - leftval + 1;
rightval += arr[left-1] - leftval + 1;
leftval += arr[left-1] - leftval + 1;
leftval -= 1;
left--;
}
}
else{
if (arr[right+1] < rightval){
rightval = arr[right+1]; right++;
}
else{
inc += arr[right+1] - rightval + 1;
leftval += arr[right+1] - rightval + 1;
rightval += arr[right+1] - rightval + 1;
rightval -= 1;
right++;
}
}
}
//cout << inc << ' ';
ans = min(inc, ans);
/*
int increase[n]; memset(increase, 0, sizeof(increase));
int runningmax = -1;
for (int x = 0; x <= k; x++){
if (arr[x] <= runningmax+1) increase[x] = runningmax - arr[x] + 1;
if (arr[x]+increase[x] > runningmax) runningmax = arr[x]+increase[x];
}
int initkInc = increase[k];
runningmax = -1;
for (int x = n-1; x >= k; x--){
if (arr[x] <= runningmax+1) increase[x] = runningmax - arr[x] + 1;
if (arr[x]+increase[x] > runningmax) runningmax = arr[x]+increase[x];
}
increase[k] = max(increase[k], initkInc);
if (k != 0) increase[k] = max(increase[k-1], increase[k]);
if (k != n-1) increase[k] = max(increase[k+1], increase[k]);
int runsum = 0;
int curHeight = 0;
for (int x = 0; x < n; x++){
if (curHeight > increase[x]){
curHeight = increase[x];
}
else if (curHeight < increase[x]){
runsum += increase[x] - curHeight, curHeight = increase[x];
}
}
cout << k << '\n';
for (int x = 0; x < n; x++) cout << arr[x] + increase[x] << ' ';
cout << '\n';
cout << runsum << "\n\n";
ans = min(ans, runsum);
* */
}
cout << ans;
//theory: can we always set max point as the k? no lol??
}
Compilation message (stderr)
Main.cpp:4:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
4 | main(){
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |