#include <bits/stdc++.h>
#include "festival.h"
using namespace std;
#define ll long long
vector<int> max_coupons(int a,vector<int> p,vector<int> t){
vector<pair<int,int>> v[5];
vector<int> u;
ll sum[200005];
double sum2[200005];
for(int i=0;i<p.size();i++){
v[t[i]].push_back({p[i],i});
}
int cnt=v[2].size()+1;
sort(v[1].begin(),v[1].end());
sort(v[2].begin(),v[2].end());
for(int i=0;i<v[2].size();i++){
if(a<(a-v[2][i].first)*2){
a=(a-v[2][i].first)*2;
u.push_back(v[2][i].second);
}
else{
cnt=i;
break;
}
}
if (cnt <= v[2].size()) {
v[2].erase(v[2].begin(), v[2].begin() + cnt);
} else {
v[2].clear();
}
int cnt1=0,cnt2=0;
int b=a;
if(v[2].size()>0){
sum2[0]=b-(a-v[2][0].first)*2;
a=(a-v[2][0].first)*2;
}
for(int i=1;i<v[2].size();i++){
sum2[i]=b-(a-v[2][i].first)*2;
a=(a-v[2][i].first)*2;
}
int pos=-1;
double *it = upper_bound(sum2,sum2+v[2].size(), a);
ll idx=it-sum2;
int ma=idx;
for(int i=0;i<v[1].size();i++){
if(i>0){
sum[i]=sum[i-1]+v[1][i].first;
}
else{
sum[i]=v[1][i].first;
}
ll x=b-sum[i];
if(x<0){
break;
}
double *it = upper_bound(sum2,sum2+v[2].size(), x);
ll idx=it-sum2;
if(ma<i+1+idx){
ma=i+1+idx;
pos=i;
}
}
for(int i=0;i<ma-pos-1;i++){
u.push_back(v[2][i].second);
}
for(int i=0;i<=pos;i++){
u.push_back(v[1][i].second);
}
return u;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |