제출 #1254464

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1254464		TadijaSebez	축제 (IOI25_festival)	C++20	27 / 100	75 ms	5704 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){
    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;
}

const ll lim=1e15;

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;
    vector<int> rem;
    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);
        }
    }
    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