Submission #1326431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326431		somefolk	Festival (IOI25_festival)	C++20	15 / 100	428 ms	887176 KiB

festival

#include <bits/stdc++.h>
using namespace std;

#define ll long long

#include <bits/stdc++.h>
using namespace std;

#define ll long long
const ll INF = (ll)1e15;
const int N = 100;

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();
    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 <= min(70, (int)v4.size()); a++){
        for(int b = 0; b <= min(70, (int)v3.size()); b++){
            for(int c = 0; c <= min(70, (int)v2.size()); c++){
                for(int d = 0; d <= min(70, (int)v1.size()); d++){
                    if(dp[a][b][c][d] < 0) continue;
                    ll curr = dp[a][b][c][d];
                    if(a < (int)v4.size() && curr >= v4[a].p){
                        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() && curr >= v3[b].p){
                        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() && curr >= v2[c].p){
                        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() && curr >= v1[d].p){
                        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(dp[a][b][c][d]>=0 && a+b+c+d > best[0]+best[1]+best[2]+best[3]) best = {a,b,c,d};
                }
            }
        }
    }

    vector<int> sol;
    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 prev = dp[best[0]-1][best[1]][best[2]][best[3]];
            if(prev >= 0){
                ll val = 4LL*(prev-v4[best[0]-1].p);
                if(val > INF) val = INF;
                if(val == rem){
                    sol.push_back(v4[best[0]-1].idx);
                    best[0]--;
                    continue;
                }
            }
        }
        if(best[1] > 0){
            ll prev = dp[best[0]][best[1]-1][best[2]][best[3]];
            if(prev >= 0){
                ll val = 3LL*(prev-v3[best[1]-1].p);
                if(val > INF) val = INF;
                if(val == rem){
                    sol.push_back(v3[best[1]-1].idx);
                    best[1]--;
                    continue;
                }
            }
        }
        if(best[2] > 0){
            ll prev = dp[best[0]][best[1]][best[2]-1][best[3]];
            if(prev >= 0){
                ll val = 2LL*(prev-v2[best[2]-1].p);
                if(val > INF) val = INF;
                if(val == rem){
                    sol.push_back(v2[best[2]-1].idx);
                    best[2]--;
                    continue;
                }
            }
        }
        if(best[3] > 0){
            ll prev = dp[best[0]][best[1]][best[2]][best[3]-1];
            if(prev >= 0){
                ll val = 1LL*(prev-v1[best[3]-1].p);
                if(val > INF) val = INF;
                if(val == rem){
                    sol.push_back(v1[best[3]-1].idx);
                    best[3]--;
                    continue;
                }
            }
        }
    }
    reverse(sol.begin(), sol.end());
    return sol;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 15 / 15
• Subtask 5: 0 / 27
• Subtask 6: 0 / 16
• Subtask 7: 0 / 18