# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
176091 | mat_v | 선물상자 (IOI15_boxes) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "boxes.h"
#define maxn 10000005
using namespace std;
typedef long long ll;
int n,k;
int niz[maxn];
int d;
set<int>s;
ll dist(int l, int r){
if(l > r)swap(l, r);
ll res = min(r - l, l + d - r);
return res;
}
long long delivery(int N, int K, int L, int p[]) {
n = N, k = K, d = L;
ff(i,1,n)niz[i] = p[i - 1];
ff(i,1,n){
s.insert(niz[i]);
}
int poz = 0;
int cap = k;
ll res = 0;
while(s.size() > 0){
if(cap == 0){
res += dist(poz, 0);
poz = 0;
cap = k;
continue;
}
int levi = *s.begin();
int desni = *s.rbegin();
int dist1 = dist(levi, poz);
int dist2 = dist(desni, poz);
int najbliza;
if(dist1 < dist2)najbliza = levi;
else najbliza = desni;
if(abs(najbliza - poz) + dist(poz, 0) <= dist(najbliza,0) + dist(poz,0)){
res += abs(najbliza - poz);
poz = najbliza;
cap--;
s.erase(najbliza);
}
else{
res += dist(poz, 0);
poz = 0;
}
}
return res;
}