Submission #1254624

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254624		erering	Festival (IOI25_festival)	C++20	100 / 100	566 ms	16812 KiB

festival

#include <bits/stdc++.h>
#include "festival.h"
using namespace std;
#define pb push_back
#define ll long long
ll tot;
struct info{
    ll p,t,i;
    friend bool operator<(info a,info b){
        ll sc1=(tot-a.p)*a.t;
        sc1=(sc1-b.p)*b.t;
        ll sc2=(tot-b.p)*b.t;
        sc2=(sc2-a.p)*a.t;
        return sc1>sc2;
    }
};
ll pref[200005],sz;
int score(ll a){
    if(sz==0 || a<pref[0])return 0;
    if(a>=pref[sz-1])return sz;
    int l=0,r=sz-1;
    while(l<r){
        int mid=(l+r+1)/2;
        if(pref[mid]<=a)l=mid;
        else r=mid-1;
    }
    if(pref[l]>a)l--;
    return l+1;
}
vector<info> v2;
int pos(ll A, std::vector<pair<int,int>> P[5]) {
    v2.clear();
    for(int i=0;i<P[2].size();i++)v2.pb({P[2][i].first,2LL,P[2][i].second});
    for(int i=0;i<P[3].size();i++)v2.pb({P[3][i].first,3LL,P[3][i].second});
    for(int i=0;i<P[4].size();i++)v2.pb({P[4][i].first,4LL,P[4][i].second});
    sort(v2.begin(),v2.end());
    for(auto j:v2){
        A=(A-j.p)*j.t;
        if(A<0)return 0;
        A=min(A,(long long)1e17);
    }
    return P[2].size()+P[3].size()+P[4].size()+score(A);
}
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
    vector<info> vec;
    tot=A;
    for(int i=0;i<T.size();i++)vec.pb({P[i],T[i],i});
    sort(vec.begin(),vec.end());
    ll rem=A;
    vector<int> og;
    vector<pair<ll,ll>> v[5];
    for(int i=0;i<vec.size();i++){
        ll sc=(rem-vec[i].p)*vec[i].t;
        if(sc>=1e16){
            for(int j=i;j<vec.size();j++)og.pb(vec[j].i);
            return og;
        }
        if(sc>=rem){
            rem=sc;
            og.pb(vec[i].i);
        }
        else{
            for(int j=i;j<vec.size();j++)v[vec[j].t].pb({vec[j].p,vec[j].i});
            break;
        }
    }
    A=rem;
    for(int i=0;i<5;i++){
        if(!v[i].empty())sort(v[i].begin(),v[i].end());
    }
    sz=(int)v[1].size();
    for(int i=0;i<sz;i++){
        pref[i]=v[1][i].first;
        if(i>0)pref[i]+=pref[i-1];
    }
    vector<int> sol;
    vector<pair<int,int>> p[5];
    for(int j=0;j<=min((int)v[2].size(),60);j++) {
        for (int k = 0; k <= min((int)v[3].size(),60); k++) {
            for (int l = 0; l <= min((int)v[4].size(),60); l++) {
                if (pos(A, p)>sol.size()) {
                    sol.clear();
                    for(auto e:v2)sol.pb(e.i);
                    for(int i=0;i<pos(A,p)-j-k-l;i++)sol.pb(v[1][i].second);
                }
                if (l != v[4].size()) p[4].pb({v[4][l].first,v[4][l].second});
            }
            p[4].clear();
            if (k != v[3].size()) p[3].pb({v[3][k].first,v[3][k].second});
        }
        p[3].clear();
        if (j != v[2].size())p[2].pb({v[2][j].first,v[2][j].second});
    }
    for(auto i:sol)og.pb(i);
    return og;
}

• 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