| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1340310 | biblicaleagle | 선물 (IOI25_souvenirs) | C++20 | 0 ms | 0 KiB |
#include "souvenirs.h"
#include <utility>
#include <vector>
const int NMAX = 100;
bool isPriced[NMAX] = {false};
int count[NMAX] = {0};
long long P[NMAX] = {0};
void price(const int N, long long M) {
auto [souvenirs, change] = transaction(M);
long long sum = M-change;
for (int souvenir : souvenirs) count[souvenir]++;
while (souvenirs.size() > 1) {
if (isPriced[souvenirs.back()]) {
sum -= P[souvenirs.back()];
souvenirs.pop_back();
} else {
price(N, sum / souvenirs.size());
}
}
int top = souvenirs.front();
P[top] = sum;
isPriced[top] = true;
for (int i = top+1; i < N; i++) {
if (not isPriced[i]) price(N, P[i-1]-1);
}
}
void buy_souvenirs(int N, long long P0) {
P[0] = P0;
isPriced[0] = true;
price(N, P0-1)
for (int i = 0; i < N; i++) {
while(count[i] < i) {
transaction(P[i]);
count[i]++;
}
}
return;
}
