Submission #1254409

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254409		TadijaSebez	Festival (IOI25_festival)	C++20	27 / 100	64 ms	6848 KiB

festival

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

vector<int> SolveSubtask5(int A,vector<int> P,vector<int> T){
    int n=P.size();
    vector<int> ans(n);
    iota(ans.begin(),ans.end(),0);
    sort(ans.begin(),ans.end(),[&](int i,int j){
        return (ll)-P[i]*T[i]*T[j]-(ll)P[j]*T[j]>(ll)-P[j]*T[j]*T[i]-(ll)P[i]*T[i];
    });
    return ans;
}

vector<int> SolveSubtask6(ll A,vector<int> P,vector<int> T){
    int n=P.size();
    array<vector<int>,5> cand;
    for(int i=0;i<n;i++){
        cand[T[i]].pb(i);
    }
    for(int i=1;i<=4;i++){
        sort(cand[i].begin(),cand[i].end(),[&](int i,int j){return P[i]>P[j];});
    }
    vector<int> ans;
    while(true){
        int bestT=0;
        ll left=-1;
        for(int i=1;i<=4;i++){
            if(cand[i].size()){
                int j=cand[i].back();
                ll now=(ll)(A-P[j])*T[j];
                if(now>=left){
                    bestT=i;
                    left=now;
                }
            }
        }
        if(bestT==0)break;
        ans.pb(cand[bestT].back());
        cand[bestT].pop_back();
        A=left;
    }
    return ans;
}

vector<int> Solve(ll A,vector<int> P,vector<int> T){
    int n=P.size();
    vector<int> ord(n);
    iota(ord.begin(),ord.end(),0);
    sort(ord.begin(),ord.end(),[&](int i,int j){
        return (ll)-P[i]*T[i]*T[j]-(ll)P[j]*T[j]>(ll)-P[j]*T[j]*T[i]-(ll)P[i]*T[i];
    });
    vector<int> ans;
    for(int i:ord){
        if(A>=P[i]){
            ans.pb(i);
            A=(A-P[i])*T[i];
        }
    }
    return ans;
}

vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
    //return SolveSubtask5(A,P,T);
    //return SolveSubtask6(A,P,T);
    return Solve(A,P,T);
}

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