Submission #1253693

#TimeUsernameProblemLanguageResultExecution timeMemory
1253693bynixFestival (IOI25_festival)C++20
43 / 100
81 ms13748 KiB
#include "bits/stdc++.h" using namespace std; #include "festival.h" typedef long long ll; const ll lim = 1e18; vector<int> max_coupons(int Al, vector<int> Pl, vector<int> Tl) { ll N = Pl.size(), A = (ll)Al; vector<ll> t1, t, temp, pre1(N+1, lim*2), R, P(N), T(N); for (int i = 0; i < N; i++) P[i] = (ll)Pl[i], T[i] = (ll)Tl[i]; for (ll i = 0; i < N; i++){ if (T[i] == 1) t1.push_back(i); else temp.push_back(i); } ll t1s = t1.size(), ts = temp.size(); sort(t1.begin(), t1.end(), [&](ll& a, ll& b){ return P[a] < P[b]; }); sort(temp.begin(), temp.end(), [&](ll& a, ll& b){ ll l = T[a]*((T[b]*P[b]) + P[a]), r = T[b]*((T[a]*P[a]) + P[b]); return l > r; }); ll i = 1; ll prev = (A - P[temp[0]]) * T[temp[0]], cur, M = A; if (prev > 0){ for (; i < ts; i++){ cur = (prev - P[temp[i]])*T[temp[i]]; if (cur < prev) break; cur = min(cur, lim); prev = cur; } if (i == ts - 1 && prev < cur) i++; for (ll j = 0; j < i; j++) R.push_back(temp[j]); M = prev; } else i = 0; map<ll, ll> f; for (; i < ts; i++){ f[T[temp[i]]]++; if (f[T[temp[i]]] <= 32) t.push_back(temp[i]); } ts = t.size(); vector<vector<ll>> dp(ts + 1, vector<ll>(ts + 1, -1)), log(ts + 1, vector<ll>(ts + 1, -1)); dp[0][0] = M; for (ll i = 1; i <= ts; i++){ for (ll j = 0; j < i; j++){ dp[i][j] = dp[i - 1][j]; if (dp[i][j] < 0) break; dp[i][j] = min(dp[i][j], lim); } for (ll j = 1; j <= i; j++){ ll val = (dp[i - 1][j - 1] - P[t[i-1]])*T[t[i-1]]; if (val >= dp[i][j]){ dp[i][j] = val; log[i][j] = j; } if (dp[i][j] < 0) break; dp[i][j] = min(dp[i][j], lim); } } pre1[0] = 0; for (ll i = 0; i < t1s; i++) pre1[i + 1] = pre1[i] + P[t1[i]], pre1[i + 1] = min(pre1[i + 1], lim); ll mc = 0ll, mt1 = 0ll, mt = 0ll, ct1 = 0ll; for (ll i = 0; i <= ts; i++){ if (dp[ts][i] < 0) break; ll pos = upper_bound(pre1.begin(), pre1.end(), dp[ts][i]) - pre1.begin(); if (pos == 0) ct1 = 0; else ct1 = min(pos - 1, t1s); if (ct1 + i > mc) mc = ct1 + i, mt1 = ct1, mt = i; } cur = mt; ll c = ts, b = 0; vector<ll> R2; while (b < mt){ if (log[c][cur] >= 0){ R2.push_back(t[c-1]); b++; } cur = mt - b, c--; } reverse(R2.begin(), R2.end()); for (auto &e: R2) R.push_back(e); for (ll i = 0; i < mt1; i++) R.push_back(t1[i]); vector<int> intR; for (auto &e: R) intR.push_back((int)e); return intR; }
#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...