比赛 |
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;
}