← 返回题目列表

AtCoder · abc275_f

I. 删除子数组

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

分数: 500 点

问题陈述

给你一个整数数组 A=(a_1,a_2,\ldots,a_N).
您可以执行以下操作任意次数(可能为零)。

  • 选择一个非空连续子数组 A,并将其从数组中删除。

对于每个 x=1,2,\ldots,M,解决以下问题:

  • 找到使元素之和的最小可能操作数 A 等于 x。 如果不可能求出元素之和 A 等于 x,打印 -1 。

请注意,空数组的元素总和为 0.

约束

  • 1 \leq N,M \leq 3000
  • 1 \leq a_i \leq 3000
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N M
a_1 \ldots a_N

输出

打印 M 行。的 i- 第行应包含以下问题的答案 x=i.


示例输入 1

4 5
1 2 3 4

示例输出 1

1
2
1
1
1

以下是实现目标的最少操作数的示例。

  • 对于 x=1,删除 a_2,a_3,a_4,以及元素之和 A 变为 x.
  • 对于 x=2,删除 a_3,a_4,然后删除 a_1,以及元素之和 A 变为 x.
  • 对于 x=3,删除 a_3,a_4,以及元素之和 A 变为 x.
  • 对于 x=4,删除 a_1,a_2,a_3,以及元素之和 A 变为 x.
  • 对于 x=5,删除 a_2,a_3,以及元素之和 A 变为 x.

示例输入 2

1 5
3

示例输出 2

-1
-1
0
-1
-1

示例输入 3

12 20
2 5 6 5 2 1 7 9 7 2 5 5

示例输出 3

2
1
2
2
1
2
1
2
2
1
2
1
1
1
2
2
1
1
1
1