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