제출 #1276480

#제출 시각아이디문제언어결과실행 시간메모리
1276480mehrzad축제 (IOI25_festival)C++17
0 / 100
1006 ms2162688 KiB
#include "festival.h" #include <bits/stdc++.h> using namespace std; struct Coupon { int idx; // original index long long P; // price int T; // type (multiplier) long long num; // T * P int den; // T - 1 (0 for T == 1, meaning infinite key) }; static const __int128 INF = (__int128)4'000'000'000'000'000'000LL; // sufficiently large 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].idx = i; cur[i].P = P[i]; cur[i].T = T[i]; cur[i].num = (long long)T[i] * (long long)P[i]; cur[i].den = T[i] - 1; // 0 for T==1 } // sort by increasing v = T*P/(T-1); treat T==1 as +infinity sort(cur.begin(), cur.end(), [](const Coupon& a, const Coupon& b) { if (a.den == 0 && b.den == 0) { // both type 1, order by price (cheapest first, any tie is fine) return a.P < b.P; } if (a.den == 0) return false; // a is type 1 -> larger key if (b.den == 0) return true; // b is type 1 -> larger key __int128 lhs = (__int128)a.num * b.den; __int128 rhs = (__int128)b.num * a.den; if (lhs != rhs) return lhs < rhs; // tie‑break by price return a.P < b.P; }); // DP: dp[i][k] = maximal tokens after considering first i coupons and buying exactly k of them vector<vector<__int128>> dp(N + 1, vector<__int128>(N + 1, -1)); vector<vector<char>> take(N + 1, vector<char>(N + 1, -1)); // 1 = taken, 0 = skipped dp[0][0] = A; for (int i = 0; i < N; ++i) { const Coupon& c = cur[i]; for (int k = 0; k <= i; ++k) { if (dp[i][k] < 0) continue; // Skip this coupon if (dp[i][k] > dp[i + 1][k]) { dp[i + 1][k] = dp[i][k]; take[i + 1][k] = 0; } // Take this coupon if affordable if (dp[i][k] >= (__int128)c.P) { __int128 newToken = (dp[i][k] - (__int128)c.P) * (__int128)c.T; if (newToken > INF) newToken = INF; if (newToken > dp[i + 1][k + 1]) { dp[i + 1][k + 1] = newToken; take[i + 1][k + 1] = 1; } } } } // Find the maximum number of coupons we can buy int bestK = 0; for (int k = 0; k <= N; ++k) { if (dp[N][k] >= 0) bestK = k; } // Reconstruct the sequence vector<int> revResult; int i = N, k = bestK; while (i > 0) { if (take[i][k] == 1) { revResult.push_back(cur[i - 1].idx); --k; } // if take[i][k] == 0 we simply skip this coupon --i; } reverse(revResult.begin(), revResult.end()); return revResult; }
#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...