| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1251398 | thecodingraceteam | Festival (IOI25_festival) | C++20 | 0 ms | 0 KiB |
#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;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; long long A;
if(!(cin>>n>>A)) return 0;
vector<int> P(n), T(n);
for(int i=0;i<n;i++) cin>>P[i]>>T[i];
vector<int> R=max_coupons((int)A,P,T);
cout<<R.size()<<"\n";
for(size_t i=0;i<R.size();i++){
if(i) cout<<" ";
cout<<R[i];
}
cout<<"\n";
return 0;
}