市场摊位
市场中有 N 个排成一行的摊位,从左到右编号为 1,2,…,N。其中 K 个摊位已被其他商家租用,编号为 A0,A1,…,AK−1。这些编号互不相同,但不一定按顺序给出。
你可以租用任意多个尚未被占用的摊位,也可以一个都不租。每个摊位的租金为 1。
有 N 位顾客,第 t 位顾客站在摊位 t 前。顾客会在所有已开业的摊位中选择距离最近的一个;如果左右两边的摊位距离相同,则选择编号较大的摊位。摊位之间的距离为编号之差的绝对值。
设你租用了 T 个摊位,最终有 C 位顾客选择你的摊位。给定参数 W,你的收益定义为
P=⌊NC×W⌋−T.
其中 ⌊x⌋ 表示不大于 x 的最大整数。没有租用任何摊位时,收益为 0。
给定 Q 个询问,每个询问提供一个 W。所有询问中的 N,K,A 相同,每次询问都独立选择租用方案。请分别求出最大收益。
输入格式
第一行三个整数 N,K,Q。
第二行 K 个整数 A0,A1,…,AK−1。当 K=0 时,该行可以为空。
第三行 Q 个整数 W1,W2,…,WQ。
输出格式
输出 Q 个整数,依次表示各询问的最大收益。
数据范围
- 1≤N≤109。
- 0≤K≤min(N,200000)。
- 1≤Ai≤N,各 Ai 互不相同。
- 1≤Q≤200000。
- 0≤Wi≤109。
时间限制:1 秒。内存限制:512 MB。
子任务
| 子任务 |
分值 |
附加限制 |
| 1 |
6 |
N=50,A=[3,45,19,40],Q=3,依次询问 W=20,7,10 |
| 2 |
8 |
N≤16,Q=1 |
| 3 |
11 |
K≤1 |
| 4 |
13 |
K≤1000,Q=1 |
| 5 |
15 |
Q=1 |
| 6 |
16 |
K≤1000,Q≤1000 |
| 7 |
18 |
W1≤W2≤⋯≤WQ |
| 8 |
13 |
无附加限制 |
样例 1
6 1 3
2
10 5 2
6 2 0
样例 1 说明
- W=10 时,租用摊位 1,4,能吸引 5 位顾客,收益为 ⌊50/6⌋−2=6。
- W=5 时,只租用摊位 3,能吸引 4 位顾客,收益为 ⌊20/6⌋−1=2。
- W=2 时,一个摊位都不租即可取得最大收益 0。
样例 2
6 2 1
1 5
6
1
只租用摊位 3 时,编号为 2,3 的顾客会选择你的摊位,收益为 ⌊12/6⌋−1=1。