問題一覧 > 通常問題

No.868 Hyper Subset Sum Problem

レベル : / AI推定難易度 : 2200 / 実行時間制限 : 1ケース 7.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 39
作問者 : e869120 / テスター : hirakich1000000007
お気に入りにしたユーザー ProblemId : 3321 / 自分の提出
問題文最終更新日: 2020-07-03 00:53:54
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 220 (順位表) の他の問題:

Problem Statement

You are given a sequence $A = [A_1, A_2, A_3, ..., A_N]$ consisting of $N$ natural numbers. You are also given an integer $K$.

You will perform $Q$ operations on it.

  • Change the $x_i$-th element of the sequence to $v_i$.


After each change, determine whether it is possible to choose some elements of the sequence so that their sum is $K$.
Here, each element of the sequence can be chosen only $1$ time.
For example, if the sequence is $[4, 4, 9]$, the sum can be made $0, 4, 8, 9, 13, 17$.

Constraints

All input data satisfy the following constraints.

  • $N$ is an integer between $1$ and $15 \ 000$, inclusive
  • $Q$ is an integer between $1$ and $15 \ 000$, inclusive
  • $K$ is an integer between $1$ and $15 \ 000$, inclusive
  • $A_i$ is an integer between $0$ and $15 \ 000$, inclusive
  • $x_i$ is an integer between $1$ and $N$, inclusive
  • $v_i$ is an integer between $0$ and $15 \ 000$, inclusive

Input

$N$ $K$
$A_1$ $A_2$ $A_3$ ... $A_N$
$Q$
$x_1$ $v_1$
$x_2$ $v_2$
$x_3$ $v_3$
...
$x_Q$ $v_Q$

Output

Output over $Q$ lines.
On the $i$-th line, output $1$ if there exists a subset whose sum is $K$ after the $i$-th operation has finished, and $0$ otherwise.

Sample

Sample 1
Input
3 8
4 4 9
3
1 4
2 5
3 3
Output
1
0
1

After the $1$st operation, the sequence is $[4, 4, 9]$. There is a way to choose elements: $4 + 4 = 8$.
After the $2$nd operation, the sequence is $[4, 5, 9]$. There is no way to choose elements with sum $8$.
After the $3$rd operation, the sequence is $[4, 5, 3]$. There is a way to choose elements: $5 + 3 = 8$.

Sample 2
Input
6 26
8 6 9 1 2 0
6
1 9
2 6
3 8
4 5
5 2
6 6
Output
1
1
1
0
0
1

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