# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
101864 | rocketninja7 | Safety (NOI18_safety) | C++14 | 405 ms | 20600 KiB |
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 <cstdio>
#include <vector>
#include <set>
using namespace std;
int main(){
int N;
long long int H;
scanf("%d%lld", &N, &H);
long long int S[N+1];
for(int i=1;i<N+1;i++){
scanf("%lld", &S[i]);
}
multiset<long long int> pointsL;
multiset<long long int> pointsR;
pointsL.insert(-1);
pointsR.insert(1000000001);
long long int ans=0;
for(int i=1;i<N+1;i++){
if(S[i]<*(--pointsL.end())-H*i){
pointsL.insert(S[i]+H*i);
pointsL.insert(S[i]+H*i);
pointsR.insert((*(--pointsL.end()))-2*H*i);
pointsL.erase(--pointsL.end());
ans+=(*pointsR.begin())+H*i-S[i];
}
else if(S[i]>*pointsR.begin()+H*i){
pointsR.insert(S[i]-H*i);
pointsR.insert(S[i]-H*i);
pointsL.insert((*pointsR.begin())+2*H*i);
pointsR.erase(pointsR.begin());
ans+=S[i]-(*(--pointsL.end()))+H*i;
}
else{
pointsL.insert(S[i]+H*i);
pointsR.insert(S[i]-H*i);
}
}
printf("%lld", ans);
return 0;
}
Compilation message (stderr)
# | 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... |