比赛 EYOI暨SBOI暑假快乐赛2nd 评测结果 AAAAAAAAAAAAAAAAAAAAA
题目名称 最近的母牛获胜 最终得分 100
用户昵称 ムラサメ 运行时间 4.518 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2022-06-26 08:51:29
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const long long N=2e5+10;
struct point{
	long long p,t;
}d[N];
long long k,m,n,a[N],b[N][2],f[N*2],ss[N],e[N];
long long cmp(point a,point b){
	return a.p<b.p;
}
long long cmpp(long long a,long long b){
	return a>b;
}
int main(){
	freopen("Closest_Cow_Wins.in","r",stdin);
	freopen("Closest_Cow_Wins.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>k>>m>>n;
	for(long long i=1;i<=k;i++){
		cin>>d[i].p>>d[i].t;
		e[i]=d[i].p;
	}
	for(long long i=1;i<=m;i++){
		cin>>a[i];
	}
	sort(a+1,a+m+1);
	sort(d+1,d+k+1,cmp);
	sort(e+1,e+k+1);
	for(long long i=1;i<=k;i++){
		ss[i]=ss[i-1]+d[i].t;
	}
	long long p=1;
	for(long long i=1;i<=k&&d[i].p<a[1];i++){
		p++;
		b[0][0]+=d[i].t;
	}
	for(long long i=1;i<m;i++){
		while(a[i]==d[p].p){
			p++;
		}
		long long s=0,q=p,sum=0,maxn=0;
		for(long long j=p;j<=k&&d[j].p<a[i+1];j++){
			b[i][1]+=d[j].t;
			s+=d[j].t;
			q++;
		}
		for(long long j=p;j<q;j++){
			long long l=2*d[j].p-a[i]-1;
			long long r=(l+a[i+1])/2;
			long long 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(long long 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];
	long long cnt=0;
	for(long long 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);
	long long ans=0;
	for(long long i=1;i<=n;i++){
		ans+=f[i];
	}
	cout<<ans<<endl;
	return 0;
}