No.1890 Many Sequences Sum Queries
タグ : / 解いたユーザー数 54
作問者 :
matcharate12
/ テスター :
Luke02561
追記
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もしくは右上の雲マークをクリックしてアカウントを作成してください。