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 ll;
typedef pair<ll, ll> pl;
const ll maxC = 5010;
ll n, h;
vector<ll> diffs;
ll res = 1e18;
ll median = 0;
void solve() {
vector<ll> a;
for(int i = 0; i < n; i++) {
ll aa;
cin>>aa;
a.push_back(aa);
median+=aa;
}
median=(median+n/2)/n;
res = 0;
for(auto i : a) {
res+=abs(i-median);
}
cout<<res<<"\n";
}
int main() {
ios_base::sync_with_stdio(false);cin.tie(nullptr);
cin>>n>>h;
/*if(h==0) {
solve();
return 0;
}*/
ll aa;
cin>>aa;
for(int i = 0; i < n-1; i++) {
ll bb;
cin>>bb;
diffs.push_back(bb-aa);
//cout<<diffs.back()<<" ";
aa=bb;
}
//cout<<"\n\n\n";
for(int x = -5*maxC; x <= 5*maxC; x++) {
//cout<<"doing: "<<x<<"\n";
vector<ll> tmp;
for(int i = 0; i < n-1; i++) {
tmp.push_back(diffs[i]);
}
ll lRes = abs(x);
tmp[0]+=x;
tmp.push_back(0);
for(int i = 0; i < n-1; i++) {
if(tmp[i]==0)continue;
ll v = abs(tmp[i]);
if(h>=v)continue;
ll di = v-h;
if(tmp[i]<0) {
tmp[i]+=di;
tmp[i+1]-=di;
}else if(tmp[i]>0) {
tmp[i]-=di;
tmp[i+1]+=di;
}
//cout<<i<<" "<<di<<" "<<tmp[i]<<"\n";
lRes+=di;
}
res=min(res, lRes);
}
cout<<res<<endl;
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... |