| 比赛 | 
    EYOI暨SBOI暑假快乐赛2nd | 
    评测结果 | 
    WEEEEEEEEEEEEEEEEEEEE | 
    | 题目名称 | 
    最近的母牛获胜 | 
    最终得分 | 
    0 | 
    | 用户昵称 | 
    䱖虁職 | 
    运行时间 | 
    4.317 s  | 
    | 代码语言 | 
    C++ | 
    内存使用 | 
    0.00 MiB  | 
    | 提交时间 | 
    2022-06-26 09:44:21 | 
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
typedef long long ll;
int k,m,n,p[maxn],t[maxn];
int l[maxn],w[maxn<<1]={0},ma[maxn<<1]={0};
ll ans=0;
int main(){
    freopen("Closest_Cow_Wins.in","r",stdin);
    freopen("Closest_Cow_Wins.out","w",stdout);
    scanf("%d%d%d",&k,&m,&n);
    for(int i=1;i<=k;i++)
        scanf("%d%d",&p[i],&t[i]);
    for(int i=1;i<=m;i++)
    {
        int a;
        scanf("%d",&a);
        ma[a]=1;
    }
    for(int i=1;i<=k;i++)
    {
        for(int j=0;;j++)
        {
            if(ma[p[i]+j]==1||ma[p[i]-j]==1)
            {
                l[i]=j-1;
                break;
            }
            w[p[i]+j]=w[p[i]-j]=t[i];
        }
    }
    for(int i=1;i<=n;i++)
    {
        ll maxx=0,pos;
        for(int j=0;j<=(maxn<<1);j++)
        {
            if(w[j]>maxx)
            {
                pos=j;
                maxx=w[j];
            }
        }
        ans+=maxx;
        for(int j=1;j<=k;j++)
            if(pos>=p[j]-l[j]&&pos<=p[j]+l[j])
                for(int o=p[j]-l[j];o<=p[j]+l[j];o++)
                    w[o]-=t[j];
    }
    printf("%lld\n",ans);
    return 0;
}