#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
//#include "boxes.h"
llo dp[10000001];
long long delivery(int n, int k, int ll, int it[]) {
sort(it,it+n);
for(int i=0;i<n;i++){
dp[i]=-1;
}
llo l=ll;
deque<pair<llo,int>> aa;
deque<pair<llo,int>> bb;
dp[0]=min((llo)(it[0]*2),l*2-(llo)it[0]*2);
for(int i=1;i<n;i++){
llo cc=dp[i-1]+(l-it[i])*2;
while(aa.size()){
if(aa.back().a>=cc){
aa.pop_back();
}
else{
break;
}
}
aa.pb({cc,i});
cc=dp[i-1];
while(bb.size()){
if(bb.back().a>=cc){
bb.pop_back();
}
else{
break;
}
}
bb.pb({cc,i});
while(aa.size()){
if(aa.front().b<i-k){
aa.pop_front();
continue;
}
else{
break;
}
}
while(bb.size()){
if(bb.front().b<i-k){
bb.pop_front();
continue;
}
else{
break;
}
}
dp[i]=bb.front().a+min(l,(llo)it[i]*2);
dp[i]=min(dp[i],aa.front().a);
if(i<k){
dp[i]=min(dp[i],(llo)(it[i]*2));
dp[i]=min(dp[i],(llo)(l));
dp[i]=min(dp[i],(llo)(l*2-it[0]*2));
}
/*for(int j=max(0,i-k+1);j<=i;j++){
llo cost=l;
cost=min(cost,it[i]*(llo)2);
cost=min(cost,(l-it[j])*(llo)2);
if(j>0){
cost+=dp[j-1];
}
if(dp[i]==-1){
dp[i]=cost;
}
dp[i]=min(dp[i],cost);
}*/
}
return dp[n-1];
}
/*int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
return 0;
}*/
/*
g++ -o aa -O2 box.cpp grader.cpp -std=c++14
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Incorrect |
0 ms |
256 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |