比赛 |
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;
}