# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1032100 | SonicML | 선물상자 (IOI15_boxes) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <algorithm>
#include "boxes.h"
using namespace std;
typedef long long ll;
int const NMAX = 1e7;
ll preA[1 + NMAX];
ll preB[1 + NMAX];
vector <int> a;
vector <int> b;
int centre = 0;
void buildPre(int k) {
for(int i = 0;i < a.size() && i < k;i++) {
preA[i] = 2 * a[i];
}
for(int i = k;i < a.size();i++) {
preA[i] = preA[i-k] + 2 * a[i];
}
for(int i = 0;i < b.size() && i < k;i++) {
preB[i] = 2 * b[i];
}
for(int i = k;i < b.size();i++) {
preB[i] = preB[i-k] + 2 * b[i];
}
}
ll delivery(int n, int k, int l, int positions[]) {
//cerr << "Damn, not here\n";
for(int i = 0;i < n;i++) {
int pos = positions[i];
if(l % 2 == 0 && pos == l / 2) {
centre = pos;
} else if(pos <= l / 2) {
a.push_back(pos);
} else {
b.push_back(l - pos);
}
}
//cerr << "Fourth Chaos Emerald\n";
sort(a.begin(), a.end());
sort(b.begin(), b.end());
buildPre(k);
//cerr << "I am all of me!\n";
ll ans = preA[a.size()-1] + preB[b.size()-1];
int limA = a.size()-1, limB = b.size()-1;
cerr << ans << '\n';
for(int round = 1;round < (n - 1) / k + 1;round++) {
for(int j = 0;j < k;j++) {
if(preA[limA] - preA[limA-1] < preB[limB] - preB[limB-1]) {
limA--;
} else {
limB--;
}
}
ll tans = 1LL * l * round + preA[limA] + preB[limB];
ans = min(ans, tans);
}
//cerr << "Just like taking candy from a baby, which is fine by me\n";
return ans;
}