| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1326162 | somefolk | Festival (IOI25_festival) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF = (ll)4e18;
const int N = 70;
struct El {
ll p, idx;
};
ll dp[N+5][N+5][N+5][N+5];
vector<int> max_coupons(int a, vector<int> p, vector<int> t){
int n = (int)p.size();
if(n <= 70){
vector<El> v1, v2, v3, v4;
for(int i = 0; i < n; i++){
if(t[i] == 1) v1.push_back({p[i], i});
else if(t[i] == 2) v2.push_back({p[i], i});
else if(t[i] == 3) v3.push_back({p[i], i});
else v4.push_back({p[i], i});
}
sort(v1.begin(), v1.end(), [&](auto l, auto r){ return l.p < r.p; });
sort(v2.begin(), v2.end(), [&](auto l, auto r){ return l.p < r.p; });
sort(v3.begin(), v3.end(), [&](auto l, auto r){ return l.p < r.p; });
sort(v4.begin(), v4.end(), [&](auto l, auto r){ return l.p < r.p; });
for(int i = 0; i <= N; i++)
for(int j = 0; j <= N; j++)
for(int k = 0; k <= N; k++)
for(int l = 0; l <= N; l++)
dp[i][j][k][l] = -1;
dp[0][0][0][0] = a;
array<int, 4> best = {0, 0, 0, 0};
for(int a = 0; a <= (int)v4.size(); a++){
for(int b = 0; b <= (int)v3.size(); b++){
for(int c = 0; c <= (int)v2.size(); c++){
for(int d = 0; d <= (int)v1.size(); d++){
if(dp[a][b][c][d] < 0) continue;
ll curr = dp[a][b][c][d];
if(a < (int)v4.size()){
ll val = 4LL*(curr-v4[a].p);
if(val > INF) val = INF;
dp[a+1][b][c][d] = max(dp[a+1][b][c][d], val);
}
if(b < (int)v3.size()){
ll val = 3LL*(curr-v3[b].p);
if(val > INF) val = INF;
dp[a][b+1][c][d] = max(dp[a][b+1][c][d], val);
}
if(c < (int)v2.size()){
ll val = 2LL*(curr-v2[c].p);
if(val > INF) val = INF;
dp[a][b][c+1][d] = max(dp[a][b][c+1][d], val);
}
if(d < (int)v1.size()){
ll val = 1LL*(curr-v1[d].p);
if(val > INF) val = INF;
dp[a][b][c][d+1] = max(dp[a][b][c][d+1], val);
}
if(a+b+c+d > best[0]+best[1]+best[2]+best[3]) best = {a,b,c,d};
}
}
}
}
vector<int> ans;
while(best[0]+best[1]+best[2]+best[3] > 0){
ll rem = dp[best[0]][best[1]][best[2]][best[3]];
if(best[0] > 0){
ll prv = dp[best[0]-1][best[1]][best[2]][best[3]];
if(prv >= 0){
ll val = (prv - v4[best[0]-1].p) * 4LL;
if(val > INF) val = INF;
if(val == rem){
ans.push_back(v4[best[0]-1].idx);
best[0]--;
continue;
}
}
}
if(best[1] > 0){
ll prv = dp[best[0]][best[1]-1][best[2]][best[3]];
if(prv >= 0){
ll val = (prv - v3[best[1]-1].p) * 3LL;
if(val > INF) val = INF;
if(val == rem){
ans.push_back(v3[best[1]-1].idx);
best[1]--;
continue;
}
}
}
if(best[2] > 0){
ll prv = dp[best[0]][best[1]][best[2]-1][best[3]];
if(prv >= 0){
ll val = (prv - v2[best[2]-1].p) * 2LL;
if(val > INF) val = INF;
if(val == rem){
ans.push_back(v2[best[2]-1].idx);
best[2]--;
continue;
}
}
}
if(best[3] > 0){
ll prv = dp[best[0]][best[1]][best[2]][best[3]-1];
if(prv >= 0){
ll val = (prv - v1[best[3]-1].p);
if(val > INF) val = INF;
if(val == rem){
ans.push_back(v1[best[3]-1].idx);
best[3]--;
continue;
}
}
}
}
reverse(ans.begin(), ans.end());
return ans;
}
vector<El> ones, twos;
for(int i = 0; i < n; i++){
if(t[i] == 1) ones.push_back({p[i], i});
else twos.push_back({p[i], i});
}
sort(ones.begin(), ones.end(), [&](auto l, auto r){ return l.p < r.p; });
sort(twos.begin(), twos.end(), [&](auto l, auto r){ return l.p < r.p; });
int osz = (int)ones.size();
vector<ll> pref1(osz);
for(int i = 0; i < osz; i++){
if(i == 0) pref1[i] = ones[i].p;
else pref1[i] = pref1[i-1] + ones[i].p;
}
auto get = [&](ll cnt){
return (upper_bound(pref1.begin(), pref1.end(), cnt) - pref1.begin());
};
ll curr = a;
ll amount1 = get(curr), amount2 = 0;
for(int i = 0; i < (int)twos.size(); i++){
if(curr < twos[i].p) break;
curr = curr - twos[i].p;
if(curr > INF/2) curr = INF;
else curr = curr * 2;
if(curr > INF) curr = INF;
ll temp = get(curr);
if(temp + (i+1) > amount1 + amount2){
amount1 = temp;
amount2 = i+1;
}
}
vector<int> sol;
for(int i = 0; i < amount2; i++) sol.push_back(twos[i].idx);
for(int i = 0; i < amount1; i++) sol.push_back(ones[i].idx);
return sol;
}
int32_t main(){
ios_base::sync_with_stdio(false); cin.tie(nullptr);
vector<int> ans = max_coupons(13, {4, 500, 8, 14}, {1, 3, 3, 4});
for(auto &i : ans) cout << i << " ";
return 0;
}