| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1276476 | mehrzad | Festival (IOI25_festival) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
struct Coupon {
int idx; // original index
long long P; // price
int T; // multiplier (1..4)
};
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
int N = (int)P.size();
vector<Coupon> coupons;
coupons.reserve(N);
for (int i = 0; i < N; ++i) {
coupons.push_back({i, (long long)P[i], T[i]});
}
/* Sort by descending v = P * T / (T-1).
T = 1 gives v = +infinity, therefore all T=1 coupons are placed
before any T>1 coupon. */
auto cmp = [](const Coupon& a, const Coupon& b) {
if (a.T == 1 && b.T != 1) return true;
if (b.T == 1 && a.T != 1) return false;
if (a.T == 1 && b.T == 1) return a.idx < b.idx; // tie‑break
// both T > 1 : compare a.P * a.T / (a.T-1) vs b.P * b.T / (b.T-1)
__int128 left = (__int128)a.P * a.T * (b.T - 1);
__int128 right = (__int128)b.P * b.T * (a.T - 1);
if (left != right) return left > right; // descending v
return a.idx < b.idx;
};
sort(coupons.begin(), coupons.end(), cmp);
int M = (int)coupons.size();
const long long INF = (1LL << 60); // large enough
// dp[i][c] = minimal initial tokens needed after considering first i coupons
// and taking exactly c of them.
vector<vector<long long>> dp(M + 1, vector<long long>(M + 1, INF));
vector<vector<int>> prev_c(M + 1, vector<int>(M + 1, -1));
vector<vector<char>> took(M + 1, vector<char>(M + 1, 0));
dp[0][0] = 0;
prev_c[0][0] = -1;
for (int i = 0; i < M; ++i) {
const Coupon& cur = coupons[i];
for (int c = 0; c <= i; ++c) {
if (dp[i][c] == INF) continue;
// skip current coupon
if (dp[i][c] < dp[i + 1][c]) {
dp[i + 1][c] = dp[i][c];
prev_c[i + 1][c] = c;
took[i + 1][c] = 0;
}
// take current coupon (adds it at the front of the reverse order)
long long new_need = cur.P + (dp[i][c] + cur.T - 1) / cur.T; // ceil division
if (new_need < dp[i + 1][c + 1]) {
dp[i + 1][c + 1] = new_need;
prev_c[i + 1][c + 1] = c;
took[i + 1][c + 1] = 1;
}
}
}
long long A_ll = (long long)A;
int best = 0;
for (int c = M; c >= 0; --c) {
if (dp[M][c] <= A_ll) {
best = c;
break;
}
}
vector<int> answer;
if (best == 0) return answer;
// reconstruct the chosen coupons; this yields the purchase order
// (because we backtrack from the end of the descending‑v list).
int i = M;
int c = best;
while (i > 0) {
if (took[i][c]) {
answer.push_back(coupons[i - 1].idx);
c = prev_c[i][c];
} else {
c = prev_c[i][c];
}
--i;
}
// 'answer' already lists coupons in the order they should be bought.
return answer;
}
", "grade": [0.0, 7.0, 0.0, 15.0, 0.0, 0.0, 0.0], "tokens": 46284}, {"code": "#include <bits/stdc++.h>
using namespace std;
struct Coupon {
int idx; // original index
long long p; // price
int t; // type (multiplier)
};
struct Prev {
int pi; // previous i
int pc; // previous count
bool took; // was the coupon taken ?
};
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
int N = (int)P.size();
vector<Coupon> cur(N);
for (int i = 0; i < N; ++i) {
cur[i] = {i, (long long)P[i], T[i]};
}
/* sort by decreasing ratio (P*T)/(T-1), T==1 => +infinity */
auto cmp = [](const Coupon& a, const Coupon& b) {
if (a.t == 1 && b.t == 1) return a.idx < b.idx; // tie‑break
if (a.t == 1) return true; // a has larger ratio
if (b.t == 1) return false;
// both T > 1
long long left = a.p * a.t * (b.t - 1); // <= 12·10⁹, fits in 64 bit
long long right = b.p * b.t * (a.t - 1);
if (left != right) return left > right; // larger ratio first
return a.idx < b.idx;
};
sort(cur.begin(), cur.end(), cmp); // decreasing ratio
const long long INF = (1LL << 60); // far bigger than any possible need
// dp[i][c] = minimal need after first i coupons, having taken c of them
vector<vector<long long>> dp(N + 1, vector<long long>(N + 1, INF));
vector<vector<Prev>> pre(N + 1, vector<Prev>(N + 1, {-1, -1, false}));
dp[0][0] = 0;
for (int i = 0; i < N; ++i) {
long long price = cur[i].p;
int mult = cur[i].t;
for (int c = 0; c <= i; ++c) {
long long curNeed = dp[i][c];
if (curNeed == INF) continue;
// skip coupon i
if (curNeed < dp[i + 1][c]) {
dp[i + 1][c] = curNeed;
pre[i + 1][c] = {i, c, false};
}
// take coupon i
long long cand = price + ( (curNeed + mult - 1) / mult );
if (cand < dp[i + 1][c + 1]) {
dp[i + 1][c + 1] = cand;
pre[i + 1][c + 1] = {i, c, true};
}
}
}
// find maximal feasible number of coupons
int best_c = 0;
for (int c = N; c >= 0; --c) {
if (dp[N][c] <= (long long)A) {
best_c = c;
break;
}
}
if (best_c == 0) return {};
// reconstruct one optimal set (forward order = ascending ratio)
vector<int> answer;
int i = N, c = best_c;
while (i > 0) {
Prev p = pre[i][c];
if (p.pi == -1) break; // safety (should not happen)
if (p.took) {
answer.push_back(cur[i - 1].idx); // coupon i-1 was taken
}
i = p.pi;
c = p.pc;
}
// answer already in forward (ascending‑ratio) order
return answer;
}
", "grade": [0.0, 7.0, 0.0, 15.0, 0.0, 0.0, 0.0], "tokens": 39666}, {"code": "#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
using i128 = __int128_t;
struct Coupon {
int idx; // original index
int64 P; // price
int T; // type
i128 num; // P * T (for v = num / (T-1) )
int64 den; // T-1
bool inf; // true for T == 1 (v = +∞)
};
static i128 INF = ( (i128)1 << 60 ); // sufficiently large (≈10^18)
static i128 ceil_div(i128 a, int64 b) {
return (a + b - 1) / b;
}
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
int N = (int)P.size();
vector<Coupon> coupons;
coupons.reserve(N);
for (int i = 0; i < N; ++i) {
Coupon c;
c.idx = i;
c.P = P[i];
c.T = T[i];
if (c.T == 1) {
c.inf = true;
c.num = 0;
c.den = 1;
} else {
c.inf = false;
c.num = (i128)c.P * (i128)c.T; // numerator of v
c.den = c.T - 1;
}
coupons.push_back(c);
}
// sort by decreasing v (inf first)
auto cmp = [](const Coupon& a, const Coupon& b) {
if (a.inf != b.inf) return a.inf > b.inf; // inf (T==1) is larger
// compare a.num / a.den > b.num / b.den ?
// i.e. a.num * b.den > b.num * a.den
i128 left = a.num * (i128)b.den;
i128 right = b.num * (i128)a.den;
if (left != right) return left > right;
return a.idx < b.idx; // tie‑break – deterministic
};
sort(coupons.begin(), coupons.end(), cmp);
// DP[i][k] = minimal needed tokens before first i coupons,
// using exactly k of them.
vector<vector<i128>> dp(N + 1, vector<i128>(N + 1, INF));
vector<vector<char>> take(N + 1, vector<char>(N + 1, -1));
vector<vector<int>> prevK(N + 1, vector<int>(N + 1, -1));
dp[0][0] = 0; // nothing needed before empty prefix
for (int i = 0; i < N; ++i) {
const Coupon& c = coupons[i];
for (int k = 0; k <= i; ++k) {
i128 cur = dp[i][k];
if (cur == INF) continue;
/* skip c */
if (cur < dp[i + 1][k]) {
dp[i + 1][k] = cur;
take[i + 1][k] = 0;
prevK[i + 1][k] = k;
}
/* take c (it becomes the last bought coupon) */
i128 need = (i128)c.P + ceil_div(cur, c.T);
if (need < dp[i + 1][k + 1]) {
dp[i + 1][k + 1] = need;
take[i + 1][k + 1] = 1;
prevK[i + 1][k + 1] = k;
}
}
}
int bestK = 0;
for (int k = N; k >= 0; --k) {
if (dp[N][k] <= (i128)A) { bestK = k; break; }
}
// reconstruction
vector<int> answer;
int i = N, k = bestK;
while (i > 0) {
char wasTaken = take[i][k];
int pk = prevK[i][k];
if (wasTaken == 1) {
answer.push_back(coupons[i - 1].idx); // this coupon is taken
}
k = pk;
--i;
}
// 'answer' was built while walking from the end of the list to the
// beginning, i.e. in increasing v order – the exact purchase order.
// No further reversal is necessary.
return answer; // may be empty
}