제출 #1276482

#제출 시각아이디문제언어결과실행 시간메모리
1276482mehrzadFestival (IOI25_festival)C++17
0 / 100
1018 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) bool inf; // true for T == 1 (key = +infinity) __int128 num; // P * T (valid only if !inf) __int128 den; // T-1 (valid only if !inf) }; static bool cmpCoupon(const Coupon& a, const Coupon& b) { if (a.inf != b.inf) // finite keys come first return !a.inf && b.inf; if (a.inf) // both infinite – any order, keep by idx return a.idx < b.idx; // compare a.num / a.den < b.num / b.den return a.num * b.den < b.num * a.den; } std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) { int N = (int)P.size(); vector<Coupon> coupons(N); for (int i = 0; i < N; ++i) { coupons[i].idx = i; coupons[i].p = P[i]; coupons[i].t = T[i]; coupons[i].inf = (T[i] == 1); if (!coupons[i].inf) { coupons[i].num = (__int128)P[i] * (__int128)T[i]; coupons[i].den = (__int128)(T[i] - 1); } } // sort by increasing key = P*T/(T-1); T==1 -> +inf sort(coupons.begin(), coupons.end(), cmpCoupon); // reverse order: we will add coupons in front of the already built suffix vector<int> orderDesc(N); // original indices in descending key order for (int i = 0; i < N; ++i) { orderDesc[i] = coupons[N - 1 - i].idx; // biggest key first } const long long INF = (1LL << 60); // large enough ( > sum of all prices ) vector<vector<long long>> dp(N + 1, vector<long long>(N + 1, INF)); vector<vector<char>> take(N + 1, vector<char>(N + 1, 0)); dp[0][0] = 0; for (int i = 1; i <= N; ++i) { int idx = orderDesc[i - 1]; long long Pi = P[idx]; int Ti = T[idx]; for (int k = 0; k <= i; ++k) { // option 1: skip this coupon long long best = dp[i - 1][k]; char used = 0; // option 2: take it if (k > 0 && dp[i - 1][k - 1] != INF) { long long prev = dp[i - 1][k - 1]; long long cand = Pi + (prev + Ti - 1) / Ti; // ceil(prev / Ti) if (cand < best) { best = cand; used = 1; } } dp[i][k] = best; take[i][k] = used; } } int bestK = 0; for (int k = N; k >= 0; --k) { if (dp[N][k] <= A) { bestK = k; break; } } // reconstruct the answer vector<int> answer; int i = N, k = bestK; while (i > 0) { if (take[i][k]) { answer.push_back(orderDesc[i - 1]); // this coupon is used --k; } --i; } // 'answer' is already in forward chronological order (lowest key first) 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...