| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1095555 | Aviansh | Boxes with souvenirs (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;
long long delivery(int n, int k, int l, int b[]) {
int split = l/2;
int lrem = 0;
int lasleft = *(upper_bound(b,b+n,l/2)-1);
int lasright = l-*upper_bound(b,b+n,l/2);
priority_queue<int, vector<int>, greater<int>>pq;
map<int,int>mp;
for(int i = 0;i<n;i++){
mp[b[i]]++;
}
for(pair<int,int>p:mp){
if(p.first>split){
break;
}
for(int i = 0;i<p.second/k;i++){
pq.push(p.first);
//cout << "pushing1: " << p.first << "\n";
}
lrem+=p.second%k;
if(lrem>=k){
pq.push(p.first);
//cout << "pushing2: " << p.first << "\n";
lrem%=k;
}
}
int rrem = 0;
for(map<int,int>::iterator it = (--mp.end());it!=mp.begin();it--){
pair<int,int>p = *it;
if(p.first<=split){
break;
}
for(int i = 0;i<p.second/k;i++){
pq.push(l-p.first);
//cout << "pushing3: " << l-p.first << "\n";
}
rrem+=p.second%k;
if(lrem>=k){
pq.push(l-p.first);
//cout << "pushing4: " << l-p.first << "\n";
rrem%=k;
}
}
long long ans = 0;
while(!pq.empty()){
int tp = pq.top();
//cout << "popped: " << tp << "\n";
pq.pop();
ans+=tp*2;
}
//cout << "ans rn: " << ans << "\n";
if(lrem||rrem){
if(lrem==0){
ans+=2*lasright;
}
else if(rrem == 0){
ans+=2*lasleft;
}
else if(lrem+rrem<=k){
ans+=l;
}
else{
ans+=min(lasleft+lasright,1LL*2*lasleft+1LL*2*lasright);
}
}
//cout << "ans after add: " << ans << "\n";
return ans;
}