제출 #1254602

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1254602		erering	축제 (IOI25_festival)	C++20	5 / 100	1096 ms	8360 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;
}
int pos(ll A, std::vector<int> P[5]) {
    vector<info> v2;
    for(int i=0;i<P[2].size();i++)v2.pb({P[2][i],2LL,i});
    for(int i=0;i<P[3].size();i++)v2.pb({P[3][i],3LL,i});
    for(int i=0;i<P[4].size();i++)v2.pb({P[4][i],4LL,i});
    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) {
    tot=A;
    vector<pair<ll,ll>> v[5];
    vector<info> v2;
    for(int i=0;i<T.size();i++){
        v[T[i]].pb({P[i],i});
    }
    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> p[5];
    vector<int> sol;
    for(int j=0;j<=v[2].size();j++) {
        for (int k = 0; k <= v[3].size(); k++) {
            for (int l = 0; l <= v[4].size(); l++) {
                if (pos(A, p)>sol.size()) {
                    sol.clear();
                    for(int i=0;i<j;i++)sol.pb(v[2][i].second);
                    for(int i=0;i<k;i++)sol.pb(v[3][i].second);
                    for(int i=0;i<l;i++)sol.pb(v[4][i].second);
                    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);
            }
            p[4].clear();
            if (k != v[3].size()) p[3].pb(v[3][k].first);
        }
        p[3].clear();
        if (j != v[2].size())p[2].pb(v[2][j].first);
    }
    return sol;
}

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