| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1339255 | khanhphucscratch | 축제 (IOI25_festival) | C++20 | 0 ms | 0 KiB |
#include "festival.h"
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int lim = 1e18;
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
//Subtask 1-3
int n = P.size();
vector<int> one, two;
for(int i = 0; i < n; i++){
if(T[i] == 1) one.push_back(i);
else two.push_back(i);
}
sort(one.begin(), one.end(), [&](const int x, const int y){return P[x] < P[y];});
sort(two.begin(), two.end(), [&](const int x, const int y){return P[x] < P[y];});
vector<int> cd(one.size());
for(int i = 0; i < cd.size(); i++){
cd[i] = P[one[i]]; if(i > 0) cd[i] += cd[i-1];
}
int ans = 0, place = 0;
for(int i = 0; i < two.size(); i++){
int p = upper_bound(cd.begin(), cd.end(), A) - cd.begin(); p = p + i;
if(ans < p){ans = p; place = i;}
A = min(lim, (A - P[two[i]]) * 2); if(A < 0) break;
}
if(A >= 0){
int p = upper_bound(cd.begin(), cd.end(), A) - cd.begin(); p = p + two.size();
if(ans < p){ans = p; place = two.size();}
}
vector<int> idxans;
for(int i = 0; i < place; i++) idxans.push_back(two[i]);
for(int i = 0; i < ans-place; i++) idxans.push_back(one[i]);
return idxans;
}