Submission #1254472

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254472		TadijaSebez	Festival (IOI25_festival)	C++20	100 / 100	68 ms	12056 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){
        if(T[i]==1 && T[j]==1)return P[i]<P[j];
        if(T[i]==1)return false;
        if(T[j]==1)return true;
        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,vector<int> rem,vector<int> t1){
    int n=P.size();
    array<vector<int>,5> cand;
    vector<int> idx(n);
    for(int i=0;i<rem.size();i++)idx[rem[i]]=i;
    for(int i:rem){
        cand[T[i]].pb(i);
    }
    cand[1]=t1;
    array<int,5> mxPtr;
    for(int i=1;i<=4;i++){
        sort(cand[i].begin(),cand[i].end(),[&](int i,int j){return P[i]<P[j];});
        ll X=A;
        for(mxPtr[i]=0;mxPtr[i]<cand[i].size();mxPtr[i]++){
            int j=cand[i][mxPtr[i]];
            if(X<P[j])break;
            X=(X-P[j])*T[j];
        }
    }
    vector<int> ans;
    for(int a=0;a<=mxPtr[2];a++){
        for(int b=0;b<=mxPtr[3];b++){
            for(int c=0;c<=mxPtr[4];c++){
                vector<int> now;
                for(int i=0;i<a;i++)now.pb(cand[2][i]);
                for(int i=0;i<b;i++)now.pb(cand[3][i]);
                for(int i=0;i<c;i++)now.pb(cand[4][i]);
                sort(now.begin(),now.end(),[&](int i,int j){return idx[i]<idx[j];});
                ll X=A;
                bool ok=true;
                for(int i:now){
                    if(X<P[i]){
                        ok=false;
                        break;
                    }
                    X=(X-P[i])*T[i];
                }
                if(ok){
                    for(int i:cand[1]){
                        if(X<P[i]){
                            break;
                        }
                        X-=P[i];
                        now.pb(i);
                    }
                    if(ans.size()<now.size()){
                        ans=now;
                    }
                }
            }
        }
    }
    return ans;
}

const ll lim=1e15;

vector<int> Solve(ll A,vector<int> P,vector<int> T){
    int n=P.size();
    vector<int> ord,rem,t1;
    for(int i=0;i<n;i++){
        if(T[i]>1)ord.pb(i);
        else t1.pb(i);
    }
    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){
        ll B=(A-P[i])*T[i];
        if(B>=A){
            ans.pb(i);
            A=B;
            A=min(A,lim);
        }else{
            rem.pb(i);
        }
    }
    vector<int> sol=SolveSubtask6(A,P,T,rem,t1);
    for(int i:sol)ans.pb(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: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 27 / 27
• Subtask 6: 16 / 16
• Subtask 7: 18 / 18