Submission #1276487

#TimeUsernameProblemLanguageResultExecution timeMemory
1276487mehrzadFestival (IOI25_festival)C++17
0 / 100
1022 ms2162688 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...