Submission #409127

#TimeUsernameProblemLanguageResultExecution timeMemory
409127pliamBoxes with souvenirs (IOI15_boxes)C++14
100 / 100
583 ms134272 KiB
#include "boxes.h" #include <bits/stdc++.h> using namespace std; #define MAXN 10000005 typedef long long ll; ll pos[MAXN]; deque<pair<int,ll>> min_q; int n,k; ll l; ll ans; ll min_(){ return min_q.front().second; } void insert_q(pair<int,ll> p){ while(!min_q.empty()&&p.second<min_q.back().second) min_q.pop_back(); min_q.push_back(p); } void erase_q(int x){ if(!min_q.empty()&&min_q.front().first==x) min_q.pop_front(); } ll dist(ll x){ return min(x,l-x); } int modn(int i){ return (i<=n)?i:(i-n); } ll c(int i){ return dist(pos[modn(i)])+pos[i]; } ll d(int i){ return dist(pos[modn(i+1)])-pos[i+1]; } long long delivery(int N, int K, int L, int positions[]) { n=N; k=K; l=L; if(N==1){ return 2*dist(positions[0]); } for(int i=1;i<=n;i++){ pos[i]=positions[i-1]; } insert_q({0,d(0)});//base case for(int i=1;i<=n;i++){ erase_q(i-k-1); ans=min_()+c(i); insert_q({i,min_()+c(i)+d(i)}); } return ans; }
#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...