제출 #1251400

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251400		thecodingraceteam	Festival (IOI25_festival)	C++20	24 / 100	76 ms	12716 KiB

festival

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

vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
    int n=P.size();
    const long long INF=4000000000000000000LL;
    vector<pair<long long,int>> g[5], v1;
    for(int i=0;i<n;i++){
        if(T[i]==1) v1.push_back({P[i],i});
        else g[T[i]].push_back({P[i],i});
    }
    sort(v1.begin(),v1.end());
    for(int t=2;t<=4;t++) sort(g[t].begin(),g[t].end());
    vector<long long> s1(v1.size());
    for(size_t i=0;i<v1.size();i++) s1[i]=(i? s1[i-1]:0)+v1[i].first;
    auto f=[&](long long x)->int{
        if(s1.empty()) return 0;
        return upper_bound(s1.begin(),s1.end(),x)-s1.begin();
    };
    priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>> h[5];
    vector<int> p(5,0), r;
    long long x=A;
    while(1){
        for(int t=2;t<=4;t++){
            while(p[t]<(int)g[t].size() && g[t][p[t]].first<=x){
                h[t].push(g[t][p[t]]);
                p[t]++;
            }
        }
        long long best=-1; int bt=-1; pair<long long,int> bi;
        int fx=f(x);
        for(int t=2;t<=4;t++){
            if(h[t].empty()) continue;
            auto cur=h[t].top();
            long long nx=(long long)(x-cur.first)*t;
            if(nx<0) nx=0;
            if(nx>INF) nx=INF;
            if(1+f(nx) < fx) continue;
            if(nx>best || (nx==best && cur.first<bi.first)){
                best=nx; bt=t; bi=cur;
            }
        }
        if(bt==-1) break;
        h[bt].pop();
        r.push_back(bi.second);
        x=best;
    }
    for(auto &e:v1){
        if(e.first<=x){
            x-=e.first;
            r.push_back(e.second);
        }else break;
    }
    return r;
}

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