昨天赛事写的,只错了056三个点,剩下43个点都对了,不太清楚哪里写挂了
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 200005;
const ll I = 1e18;
int p[N], c[N], o[N];
ll sp[N], sc[N], so[N];
int cp, cc, co;
int n, m;
ll res = 0;
bool judge(int Md, int lim)
{
int id = lower_bound(so + 1, so + co + 1, Md) - so;
// printf("s%lld m%d\n", so[id], Md);
if(so[id] < Md) return 0;
if(id + Md <= lim) return 1;
else return 0;
}
int binarysearch(int l, int r, int lim)
{
if(!judge(l, lim)) return 0;
int ans = l;
++r;
while(l < r)
{
// printf("%d %d\n", l, r);
int md = (l + r) >> 1;
if(judge(md, lim))
{
ans = max(ans, md);
l = md + 1;
}
else
{
r = md;
}
}
return ans;
}
signed main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i)
{
int t, x;
scanf("%d%d", &t, &x);
if(t == 0) p[++cp] = x;
else if(t == 1) c[++cc] = x;
else if(t == 2) o[++co] = x;
else puts("Err");
}
sort(p + 1, p + cp + 1, greater<int>() );
sort(c + 1, c + cc + 1, greater<int>() );
sort(o + 1, o + co + 1, greater<int>() );
for(int i = 1; i <= cp; ++i) sp[i] = sp[i - 1] + p[i];
for(int i = 1; i <= cc; ++i) sc[i] = sc[i - 1] + c[i];
for(int i = 1; i <= co; ++i) so[i] = so[i - 1] + o[i];
if(co == 0 || sc == 0)
{
printf("%lld", sp[cp]); return 0;
}
for(int i = 0; i <= cp; ++i)
{
int limit = m - i;
int id = binarysearch(1, cc, limit);
if(id) res = max(res, sp[i] + sc[id]);
}
printf("%lld", res);
return 0;
}