Submission #254255

#TimeUsernameProblemLanguageResultExecution timeMemory
254255eohomegrownappsBoxes with souvenirs (IOI15_boxes)C++14
100 / 100
792 ms231052 KiB
#include "boxes.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; deque<ll> dqx; deque<ll> dqxv; ll INF = 1e18; void add(ll x, deque<ll> &dq){ while (dq.size()>0&&dq.front()>x){ dq.pop_front(); } dq.push_front(x); } ll getMin(deque<ll> &dq){ return dq.back(); } void remove(ll x, deque<ll> &dq){ if (dq.size()>0&&dq.back()==x){ dq.pop_back(); } } ll delivery(int n, int k, int l, int p[]) { vector<ll> dp(n+1,INF); dp[n]=0; add(2*p[n-1]+dp[n],dqxv); add(dp[n],dqx); for (int i = n-1; i>=0; i--){ dp[i]=min(dp[i],getMin(dqxv)); dp[i]=min(dp[i],2*l-2*p[i]+getMin(dqx)); dp[i]=min(dp[i],l+getMin(dqx)); //cout<<i<<' '<<dp[i]<<'\n'; if (i==0){break;} //remove if (i+k-1<n){ remove(dp[i+k],dqx); remove(2*p[i+k-1]+dp[i+k],dqxv); } //add add(dp[i],dqx); add(2*p[i-1]+dp[i],dqxv); } return dp[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...