| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1095555 | Aviansh | 선물상자 (IOI15_boxes) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}