| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 678457 | hello_there_123 | 선물상자 (IOI15_boxes) | C++17 | 0 ms | 0 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 <bits/stdc++.h>
//#include "boxes.h"
using namespace std;
#define int long long
int delivery(int n, int k, int l, int p[])
{
int pre[l+3],pre2[l+3];
memset(pre,0,sizeof(pre));
memset(pre2,0,sizeof(pre2));
deque<int>left,right;
for(int i=0;i<n;i++){
if(p[i]<=l/2) left.push_front(p[i]);
else{
right.push_back(l-p[i]);
}
}
sort(right.begin(),right.end());
for(int i=0;i<left.size();i++){
pre[(left.size()-i-1)%k]+=left[i];
}
for(int i=0;i<right.size();i++){
pre2[(right.size()-i-1)%k]+=right[i];
}
int ans = 1e9;
for(int i=0;i<(n+l-1)/k;i++){
int cur = i*l;
cur+=2*(pre[(left.size()-1)%k]+pre2[(right.size()-1)%k]);
ans = min(ans,cur);
for(int j=0;j<k;j++){
if(left.empty() && right.empty()) break;
if(left.empty()){
pre2[(right.size()-1)%k]-=right.front();
right.pop_front();
}
else if(right.empty()){
pre[(left.size()-1)%k]-=left.front();
left.pop_front();
}
else{
if(left.front()>right.front()){
pre[(left.size()-1)%k]-=left.front();
left.pop_front();
}
else{
pre2[(right.size()-1)%k]-=right.front();
right.pop_front();
}
}
}
}
return ans;
}