比赛 |
EYOI暨SBOI暑假快乐赛2nd |
评测结果 |
AEEEEEEEEEEEEEEEEEEEE |
题目名称 |
最近的母牛获胜 |
最终得分 |
4 |
用户昵称 |
lihaoze |
运行时间 |
5.163 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2022-06-26 11:54:24 |
显示代码纯文本
#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];
i64 a[N];
PII s[N];
bool st[N];
struct Node {
i64 v, fi, se;
};
std::vector<Node> v;
i64 c[N], tot;
i64 lowbit(i64 x) { return x & -x; }
i64 ask(i64 x) {
i64 y = 0;
for (; x; x -= lowbit(x)) y += c[x];
return y;
}
void insert(i64 x, i64 y) {
for (; x < tot; x += lowbit(x)) c[x] += y;
}
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];
insert(f[i], 1);
}
std::sort(f + 1, f + 1 + m);
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 sum = std::abs(f[a[i - 1]] - y) + std::abs(f[a[i] + 1] - x);
if (x && !(ask(y) - ask(x - 1)) && (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;
}