比赛 EYOI暨SBOI暑假快乐赛2nd 评测结果 AEEEEEEEEEEEEEEEEEEEE
题目名称 最近的母牛获胜 最终得分 4
用户昵称 cb 运行时间 5.965 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2022-06-26 11:04:17
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
int k, m, n;

struct thing {
    int W;
}zu[MAXN];

struct cao {
    int nearest, pos, p, fa;
    bool kao;
}x[MAXN];

bool cmp (cao r1, cao r2) {
    return r1.pos < r2.pos;
}

bool cmp1 (thing r1, thing r2) {
    return r1.W > r2.W;
}

int main () {
    freopen ("Closest_Cow_Wins.in", "r", stdin);
    freopen ("Closest_Cow_Wins.out", "w", stdout);
    cin >> k >> m >> n;
    for (int q = 1; q <= k; ++q) {
        cin >> x[q].pos >> x[q].p;
        x[q].fa = q;
        x[q].nearest = 1e9 + 5;
        x[q].kao = false;
    }
    for (int q = 1; q <= m; ++q) {
        x[q + k].kao = true;
        cin >> x[q + k].pos;
    }
    sort (x + 1, x + k + m + 1, cmp);
//    if (x[k + m].kao == false) {
//        m ++;
//        x[k + m].kao = true;
//        x[k + m].pos = 2e9 + 2; 
//    }
    int pk = -1;
    for (int q = 1; q <= k + m; ++q) {
//        x[q].kao ? printf ("cow %d\n", x[q].pos) : printf ("cao %d %d\n", x[q].pos, x[q].nearest);
        if (x[q].kao) {
            pk = x[q].pos;
            int xx = q - 1;
            while (x[xx].kao == false && pk - x[xx].pos < x[xx].nearest && xx > 0) {
                x[xx].nearest = pk - x[xx].pos;
                xx --;
            }
        }
        else {
            if (pk != -1) {
                x[q].nearest = min (x[q].nearest, x[q].pos - pk);
            }
        }
    }
    memset (zu ,0xcf, sizeof (zu));
//    printf ("\n");
//    for (int q = 1; q <= k + m; ++q) {
//        x[q].kao ? printf ("cow %d\n", x[q].pos) : printf ("cao %d %d q:%d\n", x[q].pos, x[q].nearest, x[q].p);
//    }
    int val = 0, mx = -1, nzu = 0, top, tail;
    bool fir = false;
    
    for (int q = 1; q <= k + m; ++q) {
        if (q == 1 && x[q].kao == false) {
            val += x[q].p;
            fir =  true;
        }
        if (x[q].kao == false) {
            if (val == 0) top = q;
            else tail = q;
            val += x[q].p;
            mx = max (mx, x[q].p);
        }
        if (x[q].kao == true) {
            if (fir == true) {
                fir = false;
                zu[++ nzu].W = val;
            }
            else {
                if (val != 0) {
                    if (x[tail].pos - x[top].pos > x[tail].nearest + x[top].nearest) {
                        zu[++ nzu].W = val; 
                        val = 0; mx = -1;
                    }
                    else {
                        zu[++ nzu].W = mx;
                        val = 0; mx = -1;
                    }
                }
            }
        }
    }
    if (val != 0) {
        zu[++ nzu].W = val; 
        val = 0; mx = -1;
    }
    sort (zu + 1, zu + nzu + 1, cmp1);
//    for (int q = 1; q <= nzu; ++q) {
//        printf ("%d ", zu[q].W);
//    }
//    printf ("\n");
    long long ans = 0;
    for (int q = 1; q <= n; ++q) {
        ans += zu[q].W;
    }
    cout << ans << endl;
    return 0;
}