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;
typedef long long int llint;
const int MAXN=5010;
const llint inf=1e18;
int n;
int h[MAXN];
llint sol=inf;
llint f(int v,int idx){
llint ret=0;
for(int i=0;i<n;i++){
int eh=v-abs(idx-i);
ret+=abs(eh-h[i]);
}
return ret;
}
llint solve(int idx){
int lo=max(idx+1,n-idx),hi=1e9,mid;
while(lo<hi){
mid=(lo+hi)/2;
llint f0=f(mid-1,idx);
llint f1=f(mid,idx);
llint f2=f(mid+1,idx);
if(f0<=f1&&f1<=f2) hi=mid-1;
else if(f0>=f1&&f1>=f2) lo=mid+1;
else lo=hi=mid;
}
return f(lo,idx);
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>h[i];
}
for(int i=0;i<n;i++){
sol=min(sol,solve(i));
}
cout<<sol<<"\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |