比赛 EYOI暨SBOI暑假快乐赛2nd 评测结果 AAAAAAAAAAAAAAAAAAAAA
题目名称 最近的母牛获胜 最终得分 100
用户昵称 ZRQ 运行时间 4.544 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2022-06-26 11:33:41
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const long long N=200050;
struct point
{
	ll p,t;
}d[N];
ll k,m,n,a[N],b[N][2],f[N*2],ss[N],e[N];
ll cmp(point a,point b)
{
	return a.p<b.p;
}
ll cmpp(ll a,ll b)
{
	return a>b;
}
int main()
{
	freopen("Closest_Cow_Wins.in","r",stdin);
	freopen("Closest_Cow_Wins.out","w",stdout);
	scanf("%lld%lld%lld",&k,&m,&n);
	for(ll i=1;i<=k;i++)
    {
		scanf("%lld%lld",&d[i].p,&d[i].t);
		e[i]=d[i].p;
	}
	for(ll i=1;i<=m;i++) scanf("%lld",&a[i]);
	sort(a+1,a+m+1);
	sort(d+1,d+k+1,cmp);
	sort(e+1,e+k+1);
	for(ll i=1;i<=k;i++) ss[i]=ss[i-1]+d[i].t;
	ll p=1;
	for(ll i=1;i<=k&&d[i].p<a[1];i++) p++,b[0][0]+=d[i].t;
	for(ll i=1;i<m;i++)
    {
		while(a[i]==d[p].p) ++p;
		ll s=0,q=p;
        ll maxn=0;
		for(ll j=p;j<=k&&d[j].p<a[i+1];j++)
        {
			b[i][1]+=d[j].t;
			s+=d[j].t;
			q++;
		}
		for(ll j=p;j<q;j++)
        {
			ll l=2*d[j].p-a[i]-1;
			ll r=(l+a[i+1])/2;
			ll pp=upper_bound(e+p+1,e+q,r)-e-1;
			maxn=max(maxn,ss[pp]-ss[j-1]);
		}
		p=q;
		b[i][0]=maxn;
	}
	while(a[n]==d[p].p) ++p;
	for(int i=p;i<=k&&d[i].p>a[m];i++) p++,b[m][0]+=d[i].t;
	b[m][1]=b[m][0];
	b[0][1]=b[0][0];
	ll cnt=0;
	for(int i=0;i<=m;i++)
    {
		f[++cnt]=b[i][0];
		f[++cnt]=b[i][1]-b[i][0];
	}
	sort(f+1,f+cnt+1,cmpp);
	ll ans=0;
	for(int i=1;i<=n;i++) ans+=f[i];
	printf("%lld\n",ans);
	return 0;
}