Submission #1276483

#TimeUsernameProblemLanguageResultExecution timeMemory
1276483mehrzad축제 (IOI25_festival)C++17
0 / 100
1016 ms2162688 KiB
#include <bits/stdc++.h> using namespace std; vector<int> max_coupons(int A, vector<int> P, vector<int> T) { struct Coupon { int idx; // original index long long p; // price int t; // type (multiplier) }; int N = (int)P.size(); vector<Coupon> c(N); for (int i = 0; i < N; ++i) c[i] = {i, (long long)P[i], T[i]}; /* Order that minimises the needed initial tokens. For T>1 the key is V = P * T / (T-1) . Coupons with T = 1 are placed at the end (they never increase tokens). */ auto cmp = [](const Coupon& a, const Coupon& b) { if (a.t == 1 && b.t == 1) return a.idx < b.idx; // any stable order if (a.t == 1) return false; // a after b if (b.t == 1) return true; // a before b // compare a.p * a.t * (b.t-1) < b.p * b.t * (a.t-1) long long left = a.p * a.t * (b.t - 1LL); long long right = b.p * b.t * (a.t - 1LL); if (left != right) return left < right; // deterministic tie‑break if (a.t != b.t) return a.t < b.t; return a.p < b.p; }; sort(c.begin(), c.end(), cmp); const long long INF = (1LL << 60); // dp[i][k] = minimal tokens needed before processing items i..N-1 // to buy exactly k coupons among them (respecting the order) vector<vector<long long>> dp(N + 1, vector<long long>(N + 1, INF)); dp[N][0] = 0; for (int i = N - 1; i >= 0; --i) { dp[i][0] = 0; for (int k = 1; k <= N - i; ++k) { long long best = dp[i + 1][k]; // skip current coupon long long prev = dp[i + 1][k - 1]; // take it if (prev != INF) { long long cand = c[i].p + ( (prev + c[i].t - 1) / c[i].t ); if (cand < best) best = cand; } dp[i][k] = best; } } long long A_ll = A; int bestK = 0; for (int k = N; k >= 0; --k) { if (dp[0][k] <= A_ll) { bestK = k; break; } } // reconstruct one optimal sequence (forward order = the order in 'c') vector<int> answer; answer.reserve(bestK); int i = 0, k = bestK; while (i < N && k > 0) { if (dp[i][k] == dp[i + 1][k]) { ++i; // skip this coupon } else { answer.push_back(c[i].idx); // take it --k; ++i; } } 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...