← 返回题目列表

AtCoder · donuts_2015_4

D. 甜甜圈拳击

中文机器翻译题面 查看原题

問題文

Natsuki Sudo,甜甜圈店员工,负责包装甜甜圈。夏希现在是K 甜甜圈 我正在尝试装入 N 盒子。盒子 i (1 ≦ i ≦ N) 的体积是 C_i 每个盒子里都有甜甜圈。 1 您可以输入一个。

夏希想要使用所有的盒子。然而,由于盒子比甜甜圈多,我决定通过将盒子嵌套在盒子中来用完盒子。确保每个盒子内恰好放置一个甜甜圈或盒子。 我决定包括 1 作品。盒子 i 是一个盒子 您可以放置一个体积小于 i 的盒子。另外,即使盒子里有其他盒子或甜甜圈,盒子也会被 计为 1 。盒子 盒子里面 i 如果输入 j ,则该框 i 和盒子 在 j 期间 C_{i} - C_{j} 必须包括缓冲材料的数量。此时,求所需缓冲材料用量之和的最小值。

夏树也很笨拙,所以她有时在包装盒子时会压碎它们。每次 Natsuki 压碎一个盒子时,请使用当时剩余的所有盒子找出包装盒子所需的缓冲材料的最小总和。夏希完全 粉碎 Q 盒子,i 一个被压成碎片的盒子就是一个盒子 D_i 。


入力

输入是按以下格式从标准输入给出的。

N K
C_1 C_2 ... C_N
Q
D_1
D_2
:
D_Q
  • 1 行中,2 整数 给出了 N (1 ≦ N ≦ 200,000), K (1 ≦ K ≦ N) 用空格分隔。这要从盒子开始 N 碎片和甜甜圈 这意味着有 K 。
  • 2 线代表盒子的体积。 N 整数由空格分隔。其中 i 第一个整数 C_i (1 ≦ C_i ≦ 200,000) 是一个盒子 表示 i 的音量。然而, 当p \neq q 什么时候 C_p \neq C_q 能被保证。
  • 3 行是一个整数,表示 Natsuki 压碎的盒子数量。 Q (0 ≦ Q ≦ N-K) 。
  • 4 从线 Q 行提供了有关 Natsuki 压碎的盒子的信息。其中 给出了 i 行包含一个整数 D_i (1 ≦ D_i ≦ N) 。这是夏希 i 一个被压成碎片的盒子就是一个盒子 D_i 。然而, 满足p \neq q 什么时候 D_p \neq D_q 能被保证。

部分点

针对此问题设置了部分分数。 如果所有满足

  • Q = 0 和 K = 2 的数据集 如果您正确回答 1 , 如果您对15 点。
  • Q = 0 的数据集 如果您正确回答 2 的回答正确,除上述之外, 输出使用所有 25 点。
  • K = 2 的数据集 如果您正确回答 3 的回答正确,除上述之外, 输出使用所有 30 点。

出力

输出是 由 Q+1 行组成。1 行中,N 盒子进行包装时所需缓冲材料数量的最小总和,2 从行 Q+1 至行 i (1 ≦ i ≦ Q) 行中,i 输出压碎第一个盒子后使用所有剩余盒子包装盒子时所需缓冲材料数量总和的最小值。还在输出末尾添加换行符。


入力例1

5 4
1 9 3 7 4
0

出力例1

1

在这种情况下,如果如图所示包装盒子,所需的缓冲材料的数量将会减少。 1 是最小值。蓝色部分代表将要插入缓冲材料的部分。

另外,在这种情况下,夏树是 1 不会被破坏。


入力例2

4 2
6 5 10 2
2
3
1

出力例2

4
1
0

在这种情况下,最好将物品包装在图中所示的盒子中。蓝色部分代表将要插入缓冲材料的部分。


入力例3

7 3
2 12 3 13 7 17 1
4
4
3
1
6

出力例3

7
6
6
5
0