Submission #1255767

#TimeUsernameProblemLanguageResultExecution timeMemory
1255767eradax축제 (IOI25_festival)C++20
0 / 100
1151 ms2162688 KiB
#include "festival.h" #include <bits/stdc++.h> using namespace std; using ll = long long; using vl = vector<ll>; using vvl = vector<vl>; using vi = vector<int>; using vvi = vector<vi>; using a3 = array<ll, 3>; using v3 = vector<a3>; #define sz(c) ((int)c.size()) vi max_coupons(int _a, vi p, vi t) { int n = sz(p); assert(n == sz(t)); ll a = _a; v3 coup; for (int i = 0; i < n; i++) { coup.push_back({p[i], t[i], i}); } sort(coup.begin(), coup.end(), [](auto lhs, auto rhs) { auto [x, y, lind] = lhs; auto [z, w, rind] = rhs; if (y == 1 && w == 1) return x < z; return x * y * (w - 1) < z * w * (y - 1); }); vvl dp(n + 1, vl(n + 1)); for (int i = 1; i < n + 1; i++) { for (int j = 1; j < n + 1; j++) { dp[i][j] = max(dp[i - 1][j], max(min((dp[i - 1][j - 1] - coup[j - 1][0]) * coup[j - 1][1], (ll)1e15), (ll)-1)); } } int i = n; int j = n; while (j >= 0 && dp[i][j] < 0) j--; if (j < 0) return {}; vi ret; for (; i > 0 && j > 0; i--) { int nj = j - (max(min((dp[i - 1][j - 1] - coup[j - 1][0]) * coup[j - 1][1], (ll)1e15), (ll)-1) == dp[i][j]); ret.push_back(coup[nj][2]); } return ret; }
#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...