← 返回题目列表

AtCoder · otemae2019_b

B. 件

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

配点: 100 点

問題

Pitaro 正在玩棋盘游戏。从左边开始 编号为 1 ~ M 被给予了一个号码 M 在旁边的一个连续的正方形中 N 件已放置。对于碎片 这些作品的编号为 1 ~ N 。 i 是质量 给出了 x_i 在。

正整数 K 。 Pitaro 的操作如下图所示。 1 ~ K 该值应乘以 1 您可以一次执行一次此操作。您可以按照任意顺序执行操作,并且某些操作可能无法执行。

操作 i (1 \leq i \leq K)

  • 从未移动过的碎片 1 选择一项,i 移动方块。
  • 换句话说,所选的片段是 a ,这件作品被聚集在一起。 a-i 或质量 将其移至 a+i 。
  • 目的地是 如果棋子超出 M 方格,则无法移动。
  • 棋子是否已放置在目的地并不重要。

Pitaro 正在尝试在某个方块中收集更多碎片。编写一个程序,在执行最佳操作时找到放置在某个方格上的最大棋子数量。

制約

  • 所有输入均为整数。
  • 1 \leq M \leq 2\,000
  • 1 \leq N \leq 2\,000.
  • 1 \leq K \leq 2\,000.
  • 1 \leq x_i \leq M (1 \leq i \leq N).

小課題

  1. (12 点) x_i = i (1 \leq i \leq N).
  2. (13 点) x_i (1 \leq i \leq N) 的可能值为 2 仅类型。
  3. (20 点) K \leq 2.
  4. (55 点)没有额外的限制。

入力

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

M N K
x_1 x_2 \cdots x_N

出力

将放置在某个方格上的最大棋子数量输出到标准输出。 1 逐行输出。


入力例 1

5 3 1
1 2 3

出力例 1

2

操作 1 和 1 中的片段 1 只需将其移至 2 即可。操作 这是最佳选择,因为它只能执行 1 是 您也可以写 1 次。


入力例 2

4 3 3
1 4 4

出力例 2

3

1 有时,一个方格中会放置多个棋子。操作 只需将其移至 3 和 1 中的片段 1 只需将其移至 4 即可。


入力例 3

4 2 2
4 1

出力例 3

2

操作 3 无法执行,因此质量 1 和质量 4 有 直到 2 件。然而,操作 1 和操作 通过执行 2 该值应乘以 1 次,您可以 2 至 该值是 2 件。


入力例 4

3 2 1
1 3

出力例 4

1

操作 2 无法执行并且操作 您只能执行 1 是 您也可以写 1 次。


入力例 5

5 3 2
2 5 4

出力例 5

3

入力例 6

10 5 4
1 4 1 8 7

出力例 6

4