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