제출 #1276469

#제출 시각아이디문제언어결과실행 시간메모리
1276469mehrzadFestival (IOI25_festival)C++17
12 / 100
1059 ms2162688 KiB
#include <bits/stdc++.h> using namespace std; using int64 = long long; using i128 = __int128_t; const int64 INF = (1LL << 60); // big enough, far larger than any price sum // multiply and subtract with saturation at INF static inline int64 apply(int64 cur, int64 price, int mult) { if (cur == INF) return INF; if (cur < price) return -1; // cannot buy i128 val = (i128)(cur - price) * mult; if (val > INF) return INF; return (int64)val; } // -------------------------------------------------------------------- struct MulCoupon { int idx; // original index int64 P; int T; }; vector<int> max_coupons(int A, vector<int> P, vector<int> T) { int N = (int)P.size(); /* -------- separate the two groups -------- */ vector<MulCoupon> mul; // T > 1 vector<pair<int64,int>> cheap; // price , index (T == 1) for (int i = 0; i < N; ++i) { if (T[i] == 1) cheap.emplace_back((int64)P[i], i); else mul.push_back({i, (int64)P[i], T[i]}); } /* -------- sort multipliers by K = P*T/(T-1) -------- */ auto cmpK = [](const MulCoupon& a, const MulCoupon& b) { // compare a.P * a.T / (a.T-1) < b.P * b.T / (b.T-1) i128 left = (i128)a.P * a.T * (b.T - 1); i128 right = (i128)b.P * b.T * (a.T - 1); return left < right; }; sort(mul.begin(), mul.end(), cmpK); int M = (int)mul.size(); /* -------- DP over the sorted multipliers -------- */ vector<vector<int64>> best(M + 1, vector<int64>(M + 1, -1)); // predecessor: {previous k , taken?} vector<vector<pair<int,bool>>> pre(M + 1, vector<pair<int,bool>>(M + 1, {-1,false})); best[0][0] = (int64)A; for (int i = 0; i < M; ++i) { for (int k = 0; k <= i; ++k) { if (best[i][k] == -1) continue; // not take coupon i if (best[i][k] > best[i + 1][k]) { best[i + 1][k] = best[i][k]; pre[i + 1][k] = {k, false}; } // take coupon i, if affordable if (best[i][k] >= mul[i].P) { int64 nxt = apply(best[i][k], mul[i].P, mul[i].T); if (nxt > best[i + 1][k + 1]) { best[i + 1][k + 1] = nxt; pre[i + 1][k + 1] = {k, true}; } } } } /* -------- cheap coupons: sort by price and prefix sums -------- */ sort(cheap.begin(), cheap.end(), [](const pair<int64,int>& a, const pair<int64,int>& b){ return a.first < b.first; }); int C = (int)cheap.size(); vector<int64> pref(C + 1, 0); for (int i = 1; i <= C; ++i) pref[i] = pref[i - 1] + cheap[i - 1].first; /* -------- choose the best number of multipliers -------- */ int bestTotal = 0; int bestK = 0; // how many multipliers are used int bestCheap = 0; // how many cheap coupons are taken for (int k = 0; k <= M; ++k) { int64 tok = best[M][k]; if (tok < 0) continue; // unreachable // maximal cheap coupons we can afford int cheapCnt = 0; if (tok >= pref[C]) cheapCnt = C; else { // binary search on prefix sums int lo = 0, hi = C; while (lo < hi) { int mid = (lo + hi + 1) >> 1; if (pref[mid] <= tok) lo = mid; else hi = mid - 1; } cheapCnt = lo; } int total = k + cheapCnt; if (total > bestTotal) { bestTotal = total; bestK = k; bestCheap = cheapCnt; } } /* -------- reconstruct the chosen multipliers -------- */ vector<int> answer; int i = M; int k = bestK; while (i > 0) { auto pr = pre[i][k]; int prevK = pr.first; bool took = pr.second; if (took) { answer.push_back(mul[i - 1].idx); // coupon i-1 was taken } k = prevK; --i; } reverse(answer.begin(), answer.end()); // correct chronological order /* -------- add the cheap coupons -------- */ for (int idx = 0; idx < bestCheap; ++idx) answer.push_back(cheap[idx].second); return answer; // possibly empty }
#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...