比赛 EYOI暨SBOI暑假快乐赛2nd 评测结果 AAAAAAAAAAAAAAAAAAAAA
题目名称 最近的母牛获胜 最终得分 100
用户昵称 yrtiop 运行时间 3.573 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2022-06-26 09:49:17
显示代码纯文本
#include <bits/stdc++.h>
#define pb emplace_back
using namespace std;
typedef long long ll;
int Ceil(double x) {
    return (int)(x - 0.49);
}
const int maxn = 2e5 + 5;
struct node {
    int x,y;
    node() {
        x = y = 0;
    }
}a[maxn],s[maxn];
int k,m,n,cnt,f[maxn];
priority_queue<ll> q;
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",&a[i].x,&a[i].y);
    for(int i = 1;i <= m;++ i)scanf("%d",&f[i]);
    sort(a + 1 , a + 1 + k , [](node x,node y){return x.x < y.x;});
    sort(f + 1 , f + 1 + m);
    int L = 1,R = k;
    ll tot = 0;
    for(;L <= k;++ L) {
        if(a[L].x >= f[1])break ;
        tot += a[L].y;
    }
    q.push(tot);
    tot = 0;
    for(;R;-- R) {
        if(a[R].x <= f[m])break ;
        tot += a[R].y;
    }
    q.push(tot);
    for(int i = 2,j = L;i <= m;++ i) {
        tot = 0;
        cnt = 0;
        ll ans = 0,sum = 0;
        for(;j <= R&&a[j].x == f[i];++ j);
        for(;j <= R&&a[j].x < f[i];++ j) {
            s[++ cnt] = a[j];
            tot += a[j].y;
        }
        int dist = Ceil((double)(f[i] - f[i - 1]) / 2.0);
        int l = 1;
        for(int r = 1;r <= cnt;++ r) {
            sum += s[r].y;
            for(;l <= r&&s[r].x - s[l].x >= dist;++ l)sum -= s[l].y;
            ans = max(ans , sum);
        }
        q.push(ans);
        q.push(tot - ans);
        for(;j <= R&&a[j].x == f[i];++ j);
    }
    ll ans = 0;
    for(;(n --)&&!q.empty();) {
        ans += q.top();
        q.pop();
    }
    printf("%lld",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}