| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1276485 | mehrzad | Festival (IOI25_festival) | C++17 | 0 ms | 0 KiB |
#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
struct Coupon {
int idx; // original index
long long price; // P[i]
int type; // T[i]
};
static const long long INF = (1LL << 60); // big enough (≈10^18)
// compute (cur - price) * type, but cap at INF
static long long apply(long long cur, long long price, int type) {
if (cur >= INF) return INF; // already "infinite"
__int128 tmp = (__int128)cur - price;
if (tmp < 0) return -1; // not enough tokens
tmp *= type;
if (tmp > INF) return INF;
return (long long)tmp;
}
// comparator for coupons with type > 1
static bool cmp_mult(const Coupon& a, const Coupon& b) {
// compare a.price * a.type / (a.type-1) with b.price * b.type / (b.type-1)
__int128 left = (__int128)a.price * a.type * (b.type - 1);
__int128 right = (__int128)b.price * b.type * (a.type - 1);
if (left != right) return left < right;
// tie‑break – larger multiplier first (does not affect correctness)
if (a.type != b.type) return a.type > b.type;
return a.price < b.price;
}
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
int N = (int)P.size();
vector<Coupon> mult; // T > 1
vector<Coupon> one; // T == 1
for (int i = 0; i < N; ++i) {
Coupon c{ i, (long long)P[i], T[i] };
if (T[i] == 1) one.push_back(c);
else mult.push_back(c);
}
sort(mult.begin(), mult.end(), cmp_mult); // ascending key
sort(one.begin(), one.end(),
[](const Coupon& a, const Coupon& b){ return a.price < b.price; });
// concatenated list
vector<Coupon> all;
all.reserve(N);
for (auto &c : mult) all.push_back(c);
for (auto &c : one) all.push_back(c);
int M = (int)all.size();
// DP tables
vector<vector<long long>> dp(M + 1, vector<long long>(M + 1, -1));
vector<vector<char>> take(M + 1, vector<char>(M + 1, 0));
dp[0][0] = A;
for (int i = 1; i <= M; ++i) {
const Coupon &c = all[i - 1];
for (int k = 0; k <= i; ++k) {
long long best = dp[i - 1][k]; // skip
char used = 0;
if (k > 0) {
long long prev = dp[i - 1][k - 1];
if (prev >= 0 && prev >= c.price) {
long long after = apply(prev, c.price, c.type);
if (after > best) {
best = after;
used = 1;
}
}
}
dp[i][k] = best;
take[i][k] = used;
}
}
// best achievable number of coupons
int bestK = 0;
for (int k = M; k >= 0; --k) {
if (dp[M][k] >= 0) { bestK = k; break; }
}
// reconstruct the answer
vector<int> answer;
int i = M, k = bestK;
while (i > 0 && k > 0) {
if (take[i][k]) {
answer.push_back(all[i - 1].idx);
--k;
}
--i;
}
reverse(answer.begin(), answer.end());
return answer;
}
", "grade": [0.0, 7.0, 0.0, 15.0, 0.0, 0.0, 0.0], "tokens": 40181}, {"code": "#include <bits/stdc++.h>
using namespace std;
struct Coupon {
int idx; // original index
long long p; // price
int t; // type (multiplier)
};
/* comparison for coupons with T > 1:
increasing K = p * t / (t-1)
(compare a.p * a.t * (b.t-1) with b.p * b.t * (a.t-1) )
*/
bool cmpK(const Coupon& a, const Coupon& b) {
// both a.t > 1 and 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;
// tie‑break – any deterministic rule is fine
if (a.t != b.t) return a.t > b.t; // larger multiplier first
return a.p > b.p; // larger price first
}
/* ------------------------------------------------------------ */
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
const int N = (int)P.size();
/* split coupons */
vector<Coupon> pos, ones;
for (int i = 0; i < N; ++i) {
if (T[i] > 1)
pos.push_back({i, P[i], T[i]});
else
ones.push_back({i, P[i], T[i]}); // T == 1
}
/* sort as proved in the analysis */
sort(pos.begin(), pos.end(), cmpK); // increasing K
sort(ones.begin(), ones.end(),
[](const Coupon& a, const Coupon& b) {
return a.p < b.p; // cheapest first
});
vector<Coupon> all;
all.reserve(N);
all.insert(all.end(), pos.begin(), pos.end());
all.insert(all.end(), ones.begin(), ones.end());
const int M = (int)all.size(); // M == N
/* DP */
const __int128 INF = (__int128)1 << 120; // huge enough
vector<vector<__int128>> dp(M + 1, vector<__int128>(M + 1, -1));
vector<vector<char>> take(M + 1, vector<char>(M + 1, 0));
dp[0][0] = (__int128)A;
for (int i = 1; i <= M; ++i) {
const Coupon& c = all[i - 1];
dp[i][0] = dp[i - 1][0];
take[i][0] = 0;
for (int k = 1; k <= i; ++k) {
/* skip */
dp[i][k] = dp[i - 1][k];
take[i][k] = 0;
/* take */
if (dp[i - 1][k - 1] != -1 && dp[i - 1][k - 1] >= c.p) {
__int128 base = dp[i - 1][k - 1] - c.p;
__int128 after;
if (base > INF / c.t) after = INF;
else after = base * (__int128)c.t;
if (after > dp[i][k]) {
dp[i][k] = after;
take[i][k] = 1;
}
}
}
}
/* best obtainable number of coupons */
int best = 0;
for (int k = M; k >= 0; --k) {
if (dp[M][k] != -1) {
best = k;
break;
}
}
/* reconstruction */
vector<int> answer;
int i = M, k = best;
while (i > 0) {
if (take[i][k]) {
answer.push_back(all[i - 1].idx);
--k;
}
--i;
}
reverse(answer.begin(), answer.end());
return answer;
}