Submission #1256122

#TimeUsernameProblemLanguageResultExecution timeMemory
1256122WeIlIaNFestival (IOI25_festival)C++20
48 / 100
161 ms162460 KiB
#include "festival.h" #include <bits/stdc++.h> using namespace std; #define MOD1 1000000007 #define MOD2 998244353 #define fir first #define sec second #define pushf push_front #define pushb push_back #define popf pop_front #define popb pop_back #define mp make_pair #define all(a) a.begin(), a.end() #define FOR1(a) for (ll _ = 0; _ < ll(a); ++_) #define FOR2(i, a) for (ll i = 0; i < ll(a); ++i) #define FOR3(i, a, b) for (ll i = a; i < ll(b); ++i) #define RFOR1(a) for (ll _ = (a)-1; _ >= ll(0); --_) #define RFOR2(i, a) for (ll i = (a)-1; i >= ll(0); --i) #define RFOR3(i, a, b) for (ll i = (b)-1; i >= ll(a); --i) #define overload3(a, b, c, d, ...) d // Always choose the fourth argument to call. Hence, which function to call is determined by the number of given arguments. #define REP(...) overload3(__VA_ARGS__, FOR3, FOR2, FOR1)(__VA_ARGS__) #define RREP(...) overload3(__VA_ARGS__, RFOR3, RFOR2, RFOR1)(__VA_ARGS__) typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; typedef pair<ll, ll> pll; typedef vector<ll> vll; typedef vector<bool> vb; typedef vector<char> vc; typedef vector<string> vs; typedef vector<pii> vpii; typedef vector<pll> vpll; typedef vector<vi> vvi; typedef vector<vll> vvll; typedef vector<vb> vvb; typedef vector<vc> vvc; typedef vector<vpii> vvpii; typedef vector<vpll> vvpll; typedef queue<int> qi; typedef queue<ll> qll; typedef queue<pii> qpii; typedef queue<pll> qpll; typedef deque<int> dqi; typedef deque<ll> dqll; typedef deque<pii> dqpii; typedef deque<pll> dqpll; typedef priority_queue<int> pqi; typedef priority_queue<ll> pqll; typedef priority_queue<pii> pqpii; typedef priority_queue<pll> pqpll; typedef priority_queue<int, vi, greater<int> > r_pqi; typedef priority_queue<ll, vll, greater<ll> > r_pqll; typedef priority_queue<pii, vpii, greater<pii> > r_pqpii; typedef priority_queue<pll, vpll, greater<pll> > r_pqpll; const int M = 45; struct coupon { ll p, t; int ind; coupon(ll _p, ll _t, int _ind) : p(_p), t(_t), ind(_ind) {} }; bool cmp(const coupon &a, const coupon &b) { if(a.t == b.t) { return a.p < b.p; } return a.p*a.t*(b.t-1) < b.p*b.t*(a.t-1); } vi max_coupons(int A, vi P, vi T) { vector<coupon> coupons, one; int n = P.size(); REP(i, n) { if(T[i] == 1) { one.emplace_back(P[i], T[i], i); continue; } coupons.emplace_back(P[i], T[i], i); } sort(all(one), cmp); vll pref(one.size() + 1); REP(i, 1, one.size()+1) { pref[i] = pref[i-1] + one[i-1].p; } n = coupons.size(); sort(all(coupons), cmp); vi ans; ll val = A; int pos = n; REP(i, n) { int p = coupons[i].p, t = coupons[i].t, ind = coupons[i].ind; //cerr<<"Processing coupon: " << p << " " << t << " " << ind << ' ' << val <<endl; if(val >= p) { ll nex = (val - p) * t; if(nex >= val) { ans.pushb(ind); val = nex; } else { pos = i; break; } } } vvll dp(n+1, vll(M, -1)), track(n+1, vll(M, 0)); REP(i, pos, n+1) { dp[i][0] = val; } REP(i, pos+1, n+1) { REP(j, 1, M) { ll nex = (dp[i-1][j-1] - coupons[i-1].p) * coupons[i-1].t; if(dp[i-1][j-1] >= coupons[i-1].p && nex > dp[i-1][j]) { dp[i][j] = nex; track[i][j] = 1; } else { dp[i][j] = dp[i-1][j]; } } } // REP(i, n+1) { // REP(j, 7) { // cout<<dp[i][j]<<' '; // } // cout<<endl; // } int best = -1, q = -1; REP(j, M) { if(dp[n][j] == -1) { continue; } int s = (upper_bound(all(pref), dp[n][j]) - pref.begin()) - 1; if(best + q < s + j) { best = s; q = j; } } vi temp; RREP(i, pos+1, n+1) { if(q >= 0 && track[i][q] == 1) { temp.pushb(coupons[i-1].ind); q--; } } reverse(all(temp)); ans.insert(ans.end(), all(temp)); REP(i, best) { ans.pushb(one[i].ind); } return ans; }
#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...