実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
正整数列 A=(a_1,a_2,\ldots,a_N) が与えられます。
あなたは次の操作を 0 回以上何度でも繰り返せます。
- A から(空でない)連続する部分列を選び、削除する。
x=1,2,\ldots,M に対し、次の問題を解いてください。
- A の要素の総和をちょうど x にするために必要な操作回数の最小値を求めてください。ただし、どのように操作を行っても A の要素の総和をちょうど x にできない場合は代わりに
-1
と出力してください。
なお、A が空である時、A の要素の総和は 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
Score : 500 points
Problem Statement
You are given an integer array A=(a_1,a_2,\ldots,a_N).
You may perform the following operation any number of times (possibly zero).
- Choose a nonempty contiguous subarray of A, and delete it from the array.
For each x=1,2,\ldots,M, solve the following problem:
- Find the minimum possible number of operations to make the sum of elements of A equal x.
If it is impossible to make the sum of elements of A equal x, print
-1
instead.
Note that the sum of elements of an empty array is 0.
Constraints
- 1 \leq N,M \leq 3000
- 1 \leq a_i \leq 3000
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N M a_1 \ldots a_N
Output
Print M lines. The i-th line should contain the answer for x=i.
Sample Input 1
4 5 1 2 3 4
Sample Output 1
1 2 1 1 1
The followings are examples of minimum number of operations that achieve the goal.
- For x=1, delete a_2,a_3,a_4, and the sum of elements of A becomes x.
- For x=2, delete a_3,a_4, then delete a_1, and the sum of elements of A becomes x.
- For x=3, delete a_3,a_4, and the sum of elements of A becomes x.
- For x=4, delete a_1,a_2,a_3, and the sum of elements of A becomes x.
- For x=5, delete a_2,a_3, and the sum of elements of A becomes x.
Sample Input 2
1 5 3
Sample Output 2
-1 -1 0 -1 -1
Sample Input 3
12 20 2 5 6 5 2 1 7 9 7 2 5 5
Sample Output 3
2 1 2 2 1 2 1 2 2 1 2 1 1 1 2 2 1 1 1 1