| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1254695 | fasterthanyou | 축제 (IOI25_festival) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
const __int128 INF = (__int128)4e18; // safe saturation
struct Coupon {
int64 P; // price
int T; // multiplier (1 … 4)
int id; // original index
};
/*-------------------------------------------------------------*/
/* mult part: choose an optimal subset by a backwards DP */
/*-------------------------------------------------------------*/
struct Node { // vertex of the implicit DAG
int64 need; // minimal start-capital for this state
int cnt; // number of multipliers selected so far
int prev; // predecessor node id (-1 for root)
int cid; // coupon index used to reach this node (-1=root)
};
using NodeId = int;
inline bool ratio_less(const Coupon& a, const Coupon& b) {
// true <=> a.P*a.T/(a.T-1) < b.P*b.T/(b.T-1) without division
return (__int128)a.P * a.T * (b.T - 1)
< (__int128)b.P * b.T * (a.T - 1);
}
vector<int> choose_multipliers(int64 A, vector<Coupon>& mult)
/* returns the *ids* of the chosen multiplier-coupons in K-order */
{
sort(mult.begin(), mult.end(), ratio_less);
/* states: need → node id that realises the *largest* count */
unordered_map<int64, NodeId> best;
vector<Node> nodes;
best.reserve(mult.size() * 2);
best[0] = 0; // empty suffix
nodes.push_back({0, 0, -1, -1});
for (int pos = (int)mult.size() - 1; pos >= 0; --pos) {
const auto& c = mult[pos];
vector<pair<int64,NodeId>> new_best; // staged updates
for (auto [need, id] : best) {
int64 need2 = c.P + (need + c.T - 1) / c.T; // ceil
int cnt2 = nodes[id].cnt + 1;
auto it = best.find(need2);
if (it == best.end() || cnt2 > nodes[it->second].cnt) {
NodeId nid = (NodeId)nodes.size();
nodes.push_back({need2, cnt2, id, c.id});
new_best.emplace_back(need2, nid);
}
}
for (auto [k,v] : new_best) best[k] = v; // commit
}
/* pick the state with need ≤ A and largest cnt */
NodeId best_id = 0;
for (auto [need, id] : best)
if (need <= A && nodes[id].cnt > nodes[best_id].cnt)
best_id = id;
/* reconstruct */
vector<int> picked;
for (NodeId v = best_id; nodes[v].prev != -1; v = nodes[v].prev)
picked.push_back(nodes[v].cid);
reverse(picked.begin(), picked.end()); // K-order
return picked;
}
/*-------------------------------------------------------------*/
/* put everything together */
/*-------------------------------------------------------------*/
vector<int> max_coupons(int A,
const vector<int>& P_in,
const vector<int>& T_in)
{
const int N = (int)P_in.size();
vector<Coupon> mult; // T > 1
vector<pair<int64,int>> flat; // {price,id}
for (int i = 0; i < N; ++i) {
if (T_in[i] == 1) flat .push_back({P_in[i], i});
else mult .push_back({P_in[i], T_in[i], i});
}
/* 1️⃣ choose multiplier subset by DP */
vector<int> chosen = choose_multipliers(A, mult);
/* move them into a handy array with (P,T,id) in execution order */
vector<Coupon> exe;
exe.reserve(chosen.size());
{
unordered_set<int> chosen_set(chosen.begin(), chosen.end());
sort(mult.begin(), mult.end(), ratio_less); // K order again
for (auto &c : mult)
if (chosen_set.count(c.id)) exe.push_back(c);
}
/* 2️⃣ run the schedule */
int64 tokens = A;
vector<int> answer;
answer.reserve(N);
/* multipliers first */
for (const auto& c : exe) {
tokens = (tokens - c.P) * c.T;
if (tokens > INF) tokens = INF; // prevent overflow
answer.push_back(c.id);
}
/* flats afterwards (cheapest first) */
sort(flat.begin(), flat.end());
for (auto [price, id] : flat)
if (price <= tokens) {
tokens -= price;
answer.push_back(id);
}
return answer;
}