問題一覧 > 通常問題

No.1861 Required Number

レベル : / AI推定難易度 : 1300 / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 99
作問者 : sushitoruna / テスター : shiomusubi496 MtSaka
お気に入りにしたユーザー ProblemId : 7428 / 自分の提出
問題文最終更新日: 2026-10-17 07:20:47
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. Back to the original
yukicoder contest 334 (順位表) の他の問題:

For this problem, we recommend using PyPy instead of Python.
It has been confirmed that the intended solution gets TLE in Python.

Problem Statement

You are given an integer sequence $A = (A_1, A_2,..., A_N)$ of length $N$.

Here, consider a sequence of positive integers $B = (B_1, B_2, \ldots, B_M)$ that satisfies all of the following conditions.

  • $1 \leq B_1 < B_2 < \cdots < B_M \leq N$
  • $\displaystyle \sum_{i=1}^M A_{B_i} = K$

Determine whether such a $B$ exists. If it does not exist, print -1;

if it exists, print the number of positive integers that are always contained in $B$, no matter how $B$ is chosen.

Input

$N$ $K$
$A_1$ $A_2$ $\cdots$ $A_N$

The input satisfies the following constraints.

  • $1 \leq N \leq 10000 = 10^4$
  • $0 \leq K \leq 1000 = 10^3$
  • $0 \leq A_i \leq K$ $(1 \leq i \leq N)$
  • If $N = 1$, then $K \geq 1$ (added by the administrators on 2026/10/17)
  • All input values are integers.

However, since this problem can also be solved under stronger constraints, the following cases are included.

  • $1 \leq N \leq 100000 = 10^5$
  • $0 \leq K \leq 100000 = 10^5$
  • $0 \leq A_i \leq K$ $(1 \leq i \leq N)$
  • If $N = 1$, then $K \geq 1$ (added by the administrators on 2026/10/17)
  • All input values are integers.

These cases are added as evil cases, so they are judged but do not affect the final verdict. Note that getting them correct does not increase your score.

Output

If no $B$ satisfying the conditions in the problem statement exists, print -1; if one exists, print the number of positive integers that are always contained in $B$, no matter how $B$ is chosen.

Sample

Sample 1
Input
5 12
1 3 5 2 4
Output
2

The sequences $B$ satisfying the conditions are the following:

$(1, 3, 4, 5), (2, 3, 5) $

There are $2$ of them, and the integers contained in both of these $2$ sequences are $3, 5$, so print $2$.

Sample 2
Input
2 1000
8 8
Output
-1

No $B$ satisfying the conditions exists.

Sample 3
Input
3 7
3 3 4
Output
1

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