Submission #1253168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253168		anfi	Festival (IOI25_festival)	C++20	5 / 100	1052 ms	2162688 KiB

festival

#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
    int n = P.size();
    struct Coupon { ll price; int mult, idx; };
    vector<Coupon> S;
    vector<pair<ll,int>> L;
    for(int i=0;i<n;i++){
        if(T[i] >= 2) S.push_back({P[i], T[i], i});
        else L.emplace_back(P[i], i);
    }
    sort(L.begin(), L.end()); 

    int m = S.size();
    vector<ll> dp(m+1, -1);
    vector<vector<int>> parent(m+1, vector<int>(m+1, -1));
    dp[0] = A;


    for(int i=0;i<m;i++){
        ll price = S[i].price;
        int mult = S[i].mult;
        int idx = S[i].idx;
        for(int j=i; j>=0; j--){
            if(dp[j] >= price) {
                ll newval = (dp[j] - price) * mult;
                if(newval > dp[j+1]){
                    dp[j+1] = newval;
                    parent[i+1][j+1] = i; 
                    parent[i+1][j] = j;   
                }
            }
        }
        for(int j=0;j<=m;j++){
            // nothing extra
        }
    }
    

    vector<vector<ll>> dp2(m+1, vector<ll>(m+1, -1));
    vector<vector<pair<int,int>>> pre(m+1, vector<pair<int,int>>(m+1, {-1,-1}));
    dp2[0][0] = A;
    for(int i=0;i<m;i++){
        ll price = S[i].price;
        int mult = S[i].mult;
        for(int j=0;j<=i;j++) if(dp2[i][j] >= 0){
            if(dp2[i][j] > dp2[i+1][j]){
                dp2[i+1][j] = dp2[i][j];
                pre[i+1][j] = {j, -1}; 
            }
            if(dp2[i][j] >= price) {
                ll val = (dp2[i][j] - price) * mult;
                if(val > dp2[i+1][j+1]){
                    dp2[i+1][j+1] = val;
                    pre[i+1][j+1] = {j, i}; 
                }
            }
        }
    }
    int bestj = 0;
    int besti = 0;
    int bestCount = 0;
    ll bestTokens = A;
    for(int j=0;j<=m;j++){
        ll tokens = *max_element(dp2[m].begin()+j, dp2[m].begin()+j+1);
        tokens = dp2[m][j];
        if(tokens < 0) continue;
        ll rem = tokens;
        int cnt1 = 0;
        for(auto &pr: L){ if(pr.first <= rem){ rem -= pr.first; cnt1++; } else break; }
        if(j + cnt1 > bestCount){ bestCount = j + cnt1; bestj = j; bestTokens = tokens; }
    }
    
    vector<int> chosen;
    int ci = m, cj = bestj;
    while(ci > 0){ auto pr = pre[ci][cj];
        if(pr.second >= 0){ 
            chosen.push_back(S[pr.second].idx);
            cj = pr.first;
        }
        ci--;
    }
    reverse(chosen.begin(), chosen.end());
    
    ll rem = bestTokens;
    for(auto &pr : L){ if(pr.first <= rem){ rem -= pr.first; chosen.push_back(pr.second); } else break; }
    return chosen;
}

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