4569: Closest Cow Wins

Memory Limit:128 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:2 Solved:2

Description

Farmer John 沿着一条高速公路拥有一个很长的农场,可以被看作类似于一维数轴。沿着农场有 $K$ 块草地($1 \leq K \leq 2\cdot 10^5$);第 $i$ 块草地位于位置 $p_i$ 并具有美味值 $t_i$($0\le t_i\le 10^9$)。Farmer John 的死对头 Farmer Nhoj 已经将他的 $M$ 头奶牛($1 \leq M \leq 2\cdot 10^5$)放在了位置 $f_1 \ldots f_M$ 。所有这些 $K+M$ 个位置均是 $[0,10^9]$ 范围内的不同整数。 Farmer John 需要选择 $N$($1\le N\le 2\cdot 10^5$)个位置(不一定是整数)放置他的奶牛。这些位置必须与 Farmer Nhoj 的奶牛已经占用的位置不同,但是 Farmer John 可以将他的奶牛放在与草地相同的位置。 拥有最靠近某个草地的奶牛的农夫拥有这一草地。如果来自两方农夫的两头奶牛距这一草地相等,则 Farmer Nhoj 拥有该草地。 给定 Farmer Nhoj 的奶牛的位置以及草地的位置和美味值,求 Farmer John 的奶牛以最优方式放置时可以达到的最大总美味值。 ## 输入格式(从终端 / 标准输入读入): 输入的第一行包含 $K$、$M$ 和 $N$。 以下 $K$ 行每行包含两个空格分隔的整数 $p_i$ 和 $t_i$。 以下 $M$ 行每行包含一个整数 $f_i$。 ## 输出格式(输出至终端 / 标准输出): 输出一个整数,表示最大总美味值。注意这个问题的答案可能无法用 32 位整数型存储,你可能需要使用 64 位整数型(例如,C 或 C++ 中的 "long long")。

Sample Input Copy

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

Sample Output Copy

36

HINT

如果 Farmer John 将奶牛放在位置 $11.5$ 和 $8$ 则他可以得到总美味值 $10+12+14=36$。 供题:Brian Dean

加入题单

上一题 下一题 算法标签: