比赛 |
EYOI暨SBOI暑假快乐赛2nd |
评测结果 |
AWWWAAAAAAAAWAAWWAAAA |
题目名称 |
最近的母牛获胜 |
最终得分 |
71 |
用户昵称 |
遥时_彼方 |
运行时间 |
2.878 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2022-06-26 11:50:11 |
显示代码纯文本
#include<bits/stdc++.h>
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define drep(x,y,z) for(int x=y;x>=z;x--)
#define ull unsigned long long
#define ll long long
using namespace std;
inline int read()
{
int x=0;bool flag=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-')flag=0;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
if(flag) return x;
return ~(x-1);
}
inline void write(int x)
{
if(x<0) {x=~(x-1);putchar('-');}
if(x>9) write(x/10);
putchar(x%10+'0');
}
////////////////////////
const int N=2e5+50;
int kc,mc,nc;
struct K
{
ull t;
int p;
}k[N];//草地
int f[N];//母牛
ull a[N<<1],aj;
ull ans;
bool cmp(K x,K y){return x.p<y.p;}
inline void solve1()
{
int k1=1,k2=1,k3;
int f1=0,f2=1;
ull sum1,sum2,sum3;
while(f2<mc&&k1<kc)
{
while(f[f2]<k[k2].p) f1=f2++;
while(k[k2].p<f[f2]&&k2<=kc) k2++;
k2--;
//
sum1=sum2=sum3=0;
rep(i,k1,k2) sum3+=k[i].t;
//
k3=k1;
while(k[k3].p-k[k1].p<f[f2]-k[k3].p&&k3<=k2) k3++;
k3--;
rep(i,k1,k3) sum1+=k[i].t;
//
k3=k2;
while(k[k2].p-k[k3].p<k[k3].p-f[f1]&&k3>=k1) k3--;
k3++;
drep(i,k2,k3) sum2+=k[i].t;
//
if(sum1>=sum2)
{
a[++aj]=sum1;
a[++aj]=sum3-sum1;
}
else
{
a[++aj]=sum2;
a[++aj]=sum3-sum2;
}
//
k1=++k2;
}
}
int main()
{
freopen("Closest_Cow_Wins.in","r",stdin);
freopen("Closest_Cow_Wins.out","w",stdout);
kc=read(),mc=read(),nc=read();
rep(i,1,kc) k[i].p=read(),k[i].t=read();
rep(i,1,mc) f[i]=read();
sort(k+1,k+kc+1,cmp);
f[++mc]=2e9+N;
f[++mc]=-(1e9+N);
sort(f+1,f+mc+1);
solve1();
sort(a+1,a+1+aj);
drep(i,aj,aj-nc+1) ans+=a[i];
// cout<<"a:\n";
// drep(i,aj,1) cout<<a[i]<<" ";
// cout<<endl;
cout<<ans<<endl;
return 0;
}