No.868 Hyper Subset Sum Problem
タグ : / 解いたユーザー数 39
作問者 :
e869120
/ テスター :
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もしくは右上の雲マークをクリックしてアカウントを作成してください。