問題一覧 > 通常問題

No.1890 Many Sequences Sum Queries

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 61
作問者 : matcharate12 / テスター : Luke02561
お気に入りにしたユーザー ProblemId : 7225 / 自分の提出
問題文最終更新日: 2022-04-04 19:48:10
Many Sequences Sum Queries
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Show the original

Addendum

As of 4/4 17:10: There was an incorrect letter in the constraints. It should be $N$, not $n$.
As of 4/4 19:45: Following a question, a constraint on $A_i$ has been added. Note that $A_i$ is an integer greater than or equal to $1$.

Problem Statement

You are given a sequence $A$ of length $N$. There is also an empty sequence $B$.
For every $i\ (1\le i\le N)$, for the $i$-th element $A_i$ of the sequence $A$, create a sequence $P_i$ consisting only of the elements $1,…,A_i$ in this order, and insert all the elements contained in $P_i$ into $B$ in this order. After this operation, no changes of any kind may be made to $B$.
After that operation, $Q$ queries are given. The queries are as described below, so report the answers to all the queries in order.

  • In the $i\ (1\le i\le Q)$-th query, an integer $S_i$ is given. Find the minimum value of $n$ satisfying $\displaystyle\sum_{k=1}^{n}\ B_k\ge S_i$. However, if no such $n$ exists, report that fact.

Input

$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$

Output

Output $Q$ lines.
On the $i\ (1\le i\le Q)$-th line, output the answer to the $i$-th query. However, if no minimum value satisfying the condition exists, output -1.

Sample

Sample 1
Input
4 3
1 2 3 4
4
10
25
Output
3
6
-1

The sequence for $A_1$ is $P_1=(1)$, the sequence for $A_2$ is $P_2=(1,2)$, for $A_3$ it is $P_3=(1,2,3)$, and for $A_4$ it is $P_4=(1,2,3,4)$. Inserting these in order gives $B=(1,1,2,1,2,3,1,2,3,4)$.

For the $1$st query, $1+1+2=4$, so the condition is first satisfied when $n=3$.
For the $2$nd query, $1+1+2+1+2+3=10$, so the condition is first satisfied when $n=6$.
For the $3$rd query, the sum of the elements in the sequence $B$ is less than $25$, so no such $n$ exists.

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