제출 #1307847

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307847		exoworldgd	축제 (IOI25_festival)	C++20	100 / 100	77 ms	9664 KiB

festival

#include "festival.h"
#include <bits/stdc++.h>
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0)
using namespace std;
using ll=long long;
vector<int>cur,best;
int bt;
void rec(int pos,ll s,int lim,vector<int>&a,vector<pair<ll,int>>&b,vector<int>&p,vector<int>&t){
    if(lim==1||pos==a.size()){
        auto it=lower_bound(b.begin(),b.end(),make_pair(s+1,-1))-b.begin();
        if(it+cur.size()>best.size()+bt)best=cur,bt=it;
        return;
    }
    if(s>=p[a[pos]]&&lim>=t[a[pos]])cur.push_back(a[pos]),rec(pos+1,min((s-p[a[pos]])*t[a[pos]],(ll)1e18),lim,a,b,p,t),cur.pop_back();
    rec(pos+1,s,min(lim,t[a[pos]]-1),a,b,p,t);
}
vector<int>max_coupons(int A,vector<int>P,vector<int>T){
    vector<int>a;
    vector<pair<ll,int>>b;
    int n=P.size();
    for(int i=0;i<n;i++)T[i]>1?a.push_back(i):b.push_back({P[i],i});
    sort(a.begin(),a.end(),[&](int i,int j){
        if(T[i]==T[j])return P[i]<P[j];
        return 1ll*P[i]*T[i]*(T[j]-1)<1ll*P[j]*T[j]*(T[i]-1);
    });
    sort(b.begin(),b.end());
    for(int i=1;i<b.size();i++)b[i].first+=b[i-1].first;
    vector<int>res;
    ll tok=A;
    for(auto i:a){
        if((tok-P[i])*T[i]>=tok)tok=(tok-P[i])*T[i],tok=min(tok,(ll)1e15),res.push_back(i);
        else break;
    }
    a.erase(a.begin(),a.begin()+res.size()),rec(0,tok,4,a,b,P,T);
    for(auto i:best)res.push_back(i);
    for(int i=0;i<bt;i++)res.push_back(b[i].second);
    return res;
}

• 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