| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1258919 | am_aadvik | Festival (IOI25_festival) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include<vector>
#include<algorithm>
#define int long long
using namespace std;
vector<int32_t> max_coupons(int32_t a, vector<int32_t> p, vector<int32_t> t) {
int n = p.size(), v = a;
vector<pair<int, int32_t>> o[5];
for (int i = 1; i < 5; ++i) o[i].push_back({ 1e17, -1 });
for (int i = 0; i < n; ++i)
o[t[i]].push_back({ p[i], i });
for (int i = 1; i < 5; ++i)
sort(o[i].begin(), o[i].end(), greater<pair<int, int>>());
vector<vector<vector<vector<int>>>> dp(o[1].size(), vector<vector<vector<int>>>
(o[2].size(), vector<vector<int>>(o[3].size(), vector<int>(o[4].size(), 1e17))));
vector<vector<vector<vector<int>>>> par(o[1].size(), vector<vector<vector<int>>>
(o[2].size(), vector<vector<int>>(o[3].size(), vector<int>(o[4].size(), -1))));
int mx = 0, m1 = 0, m2 = 0, m3 = 0, m4 = 0;
for(int i = 0; i < o[1].size(); ++i)
for(int j = 0; j < o[2].size(); ++j)
for(int k = 0; k < o[3].size(); ++k)
for (int l = 0; l < o[4].size(); ++l) {
if (max({ i, j, k, l }) == 0) { dp[i][j][k][l] = 0; continue; }
int s = 0, e = 1e17, res = 1e17, b = -1;
while (s <= e) {
int m = (s + e) / 2, nb = -1;
bool ok = 0;
if (i > 0) ok |= (((m - o[1][i].first) * 1) >= dp[i - 1][j][k][l]); if (ok) nb = 1;
if ((j > 0) && !(ok)) { ok |= (((m - o[2][j].first) * 2ll) >= dp[i][j - 1][k][l]); if (ok) nb = 2; }
if ((k > 0) && !(ok)){ ok |= (((m - o[3][k].first) * 3ll) >= dp[i][j][k - 1][l]); if (ok) nb = 3;}
if ((l > 0) && !(ok)) {ok |= (((m - o[4][l].first) * 4ll) >= dp[i][j][k][l - 1]); if (ok) nb = 4;}
if (ok) res = m, e = m - 1, b = nb;
else s = m + 1;
}
dp[i][j][k][l] = min(res, dp[i][j][k][l]);
par[i][j][k][l] = b;
if (dp[i][j][k][l] <= v)
if ((i + j + k + l) > mx)
m1 = i, m2 = j, m3 = k,
mx = (i + j + k + l), m4 = l;
}
vector<int32_t> res;
while (max({ m1, m2, m3, m4 }) > 0) {
if (par[m1][m2][m3][m4] == 1)
res.push_back(o[1][m1--].second);
if (par[m1][m2][m3][m4] == 2)
res.push_back(o[2][m2--].second);
if (par[m1][m2][m3][m4] == 3)
res.push_back(o[3][m3--].second);
if (par[m1][m2][m3][m4] == 4)
res.push_back(o[4][m4--].second);
}
return res;
}
int32_t main() {
int n, k; cin >> n >> k;
vector<int32_t> p(n), t(n);
for (int i = 0; i < n; ++i)
cin >> p[i] >> t[i];
auto res = max_coupons(k, p, t);
for(auto x: res) cout << x << " ";
}