Submission #1054206

#TimeUsernameProblemLanguageResultExecution timeMemory
1054206KiprasSafety (NOI18_safety)C++17
0 / 100
2081 ms5604 KiB
#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; int main() { ios_base::sync_with_stdio(false);cin.tie(nullptr); cin>>n>>h; 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"; ll lowB=0, highB=0; if(diffs[0]>0) { lowB=-diffs[0]; }else { highB=diffs[0]; } for(int x = lowB; x < highB; 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...