問題一覧 > 通常問題

No.1890 Many Sequences Sum Queries

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 28
作問者 : matcharate12matcharate12 / テスター : Luke02561Luke02561
1 ProblemId : 7225 / 自分の提出
問題文最終更新日: 2022-04-04 19:48:10

追記

4/4 17:10現在 : 制約の文字を間違えておりました。 $n$ ではなく $N$ です。
4/4 19:45現在 : 質問が来ていたので、$A_i$ の制約を追加しました。$A_i$ は $1$ 以上の整数であることに注意してください。

問題文

長さ $N$ の数列 $A$ が与えられます。また空の数列 $B$ があります。
全ての $i\ (1\le i\le N)$ について、数列 $A$ に対して $i$ 番目の要素 $A_i$ において $1,…,A_i$ の要素のみでこの順で構成される数列 $P_i$ を作り、$P_i$ に含まれる要素をこの順に全て $B$ に挿入します。この操作の後、$B$ に対して何らかの変更は一切行ってはいけません。
その操作の後に $Q$ 個のクエリが与えられます。クエリの内容は以下のようになっているので、クエリに対する答えを順に全て報告して下さい。

  • $i\ (1\le i\le Q)$ 個目のクエリでは整数 $S_i$ が与えられるので、$\displaystyle\sum_{k=1}^{n}\ B_k\ge S_i$ を満たすような $n$ の最小値を求めて下さい。ただし、そのような $n$ が存在しないならその旨を報告して下さい。

入力

$N\ Q$
$A_1\ A_2\ \dots\ A_N$
$S_1$
$S_2$
$\vdots$
$S_Q$

  • $1\le N\le 100$
  • $1\le Q\le 10^5$
  • $1\le \displaystyle\sum_{i=1}^{N}\ A_i\le 10^5$
  • $1\le A_i$
  • $1\le S_i\le 10^9$

出力

$Q$ 行出力してください。
$i\ (1\le i\le Q)$ 行目には $i$ 個目のクエリの答えを出力してください。ただし、条件を満たす最小値が存在しないなら -1 を出力してください。

サンプル

サンプル1
入力
4 3
1 2 3 4
4
10
25
出力
3
6
-1

$A_1$ についての数列は $P_1=(1)$、$A_2$ についての数列は $P_2=(1,2)$、$A_3$ については $P_3=(1,2,3)$、$A_4$ については $P_4=(1,2,3,4)$ となり、これを順にそれぞれ挿入していくと $B=(1,1,2,1,2,3,1,2,3,4)$ となります。

$1$ 個目のクエリに対しては $1+1+2=4$ となり、$n=3$ の時に初めて条件を満たします。
$2$ 個目に対しては $1+1+2+1+2+3=10$ となり $n=6$ の時に初めて条件を満たします。
$3$ 個目に対しては数列 $B$ 中の要素の総和が $25$ 未満であるため、そのような $n$ は存在しません。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。