记录编号	571966	评测结果	AAAAWAAWWWAWWAAAWWAAA
题目名称	最近的母牛获胜	最终得分	61
用户昵称	lihaoze	是否通过	未通过
代码语言	C++	运行时间	2.603 s
提交时间	2022-06-26 17:05:18	内存使用	0.00 MiB

#include <bits/stdc++.h>

using i64 = long long;
using PII = std::pair<i64, i64>;

const i64 N = 4e5+10;
i64 k, m, n;
i64 f[N], a[N];
PII s[N];
std::unordered_map<i64, bool> st;

struct Node { i64 v, fi, se; };

std::vector<Node> v;

int main() {
    freopen("Closest_Cow_Wins.in", "r", stdin); 
    freopen("Closest_Cow_Wins.out", "w", stdout);
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> k >> m >> n;
    for (i64 i = 1; i <= k; ++ i) {
        auto& [x, y] = s[i];
        std::cin >> x >> y;
        v.emplace_back(Node{y, x, x});
    }
    for (i64 i = 1; i <= m; ++ i) 
        std::cin >> f[i], st[f[i]] = true;
    std::sort(f + 1, f + 1 + m);
    std::sort(s + 1, s + 1 + k);
    for (i64 i = 1; i <= k; ++ i) {
        i64 x = s[i].first, y = s[i - 1].first;
        i64 l = 1, r = m;
        while (l < r) {
            i64 mid = l + r + 1 >> 1;
            if (f[mid] <= x) l = mid;
            else r = mid - 1;
        }
        a[i] = r;
        i64 xl = f[a[i]], xr = f[a[i] + 1];
        i64 yl = f[a[i - 1]], yr = f[a[i - 1] + 1];
        i64 sum = std::abs(yl - y) + std::abs(xr - x);
        if ((yr > x || yr == 0) && x - y < sum) 
            v.emplace_back(Node{s[i].second + s[i - 1].second, x, y});
    }
    std::sort(v.begin(), v.end(), [&](Node a, Node b) { return a.v < b.v; });
    i64 res = 0;
    while (n) {
        auto x = v.back(); v.pop_back();
        if (!st[x.fi] && !st[x.se]) {
            res += x.v;
            st[x.fi] = st[x.se] = true;
            n --;
        }
    }
    std::cout << res << '\n';
    return 0;
}