昨天ABC F(wa #0 #5 #6)求助
  • 板块学术版
  • 楼主Edgebright
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/7/30 08:29
  • 上次更新2023/11/3 06:58:24
查看原帖
昨天ABC F(wa #0 #5 #6)求助
762588
Edgebright楼主2023/7/30 08:29

昨天赛事写的,只错了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;
}
2023/7/30 08:29
加载中...