Closest Cow Wins

题目描述

农夫 John 拥有一条沿着公路延伸的长农场，可以近似看作一维数轴。在农场上有 $K$ 块草地（$1 \leq K \leq 2\cdot 10^5$）；第 $i$ 块草地位于位置 $p_i$，并具有美味值 $t_i$（$0\le t_i\le 10^9$）。农夫 John 的宿敌农夫 Nhoj 已经将他的 $M$ 头牛（$1 \leq M \leq 2\cdot 10^5$）安置在位置 $f_1 \ldots f_M$。这 $K+M$ 个位置均为 $[0,10^9]$ 范围内互不相同的整数。 农夫 John 需要为他的牛选择 $N$ 个位置（$1\le N\le 2\cdot 10^5$），位置不一定是整数。这些位置必须与农夫 Nhoj 的牛所占据的位置不同，但农夫 John 可以将牛放在草地所在的位置。 对于每一块草地，距离该草地最近的那位农夫所拥有的牛可以宣称该草地的归属。如果两位农夫的牛到该草地的距离相等，则农夫 Nhoj 获得该草地。 给定农夫 Nhoj 的牛的位置，以及草地的位置与美味值，求在最优放置农夫 John 的牛的情况下，他最多能获得的总美味值。

输入格式

第一行包含 $K$、$M$ 和 $N$。 接下来 $K$ 行，每行包含两个用空格分隔的整数 $p_i$ 和 $t_i$。 接下来 $M$ 行，每行包含一个整数 $f_i$。

输出格式

输出一个整数，表示最大总美味值。注意答案可能大到无法放入 32 位整数，因此你可能需要使用 64 位整数（例如 C 或 C++ 中的 "long long"）。

6 5 2
0 4
4 6
8 10
10 8
12 12
13 14
2
3
5
7
11

36

提示

如果农夫 John 将牛放在位置 $11.5$ 和 $8$，则他可以获得的总美味值为 $10+12+14=36$。 题目来源：Brian Dean

标签: USACO|2021|Silver

来源

USACO|2021|Silver