No.868 ハイパー部分和問題
タグ : / 解いたユーザー数 35
作問者 : e869120 / テスター : hirakich1000000007
問題文
$N$ 個の自然数から成る数列 $A = [A_1, A_2, A_3, ..., A_N]$ が与えられます。また、整数 $K$ が与えられます。
さて、これについて $Q$ 回の操作を行います。
- 数列の $x_i$ 番目の要素を $v_i$ に変更する。
各変更の後について、数列のいくつかの要素を選んで合計を $K$ にする事が出来るか求めてください。
ただし、数列の各要素は $1$ 回しか選べないものとします。
例えば、数列が $[4, 4, 9]$ の場合、合計を $0, 4, 8, 9, 13, 17$ にする事が出来ます。
制約
全ての入力データは以下の制約を満たします。
- $N$ は $1$ 以上 $15 \ 000$ 以下の整数
- $Q$ は $1$ 以上 $15 \ 000$ 以下の整数
- $K$ は $1$ 以上 $15 \ 000$ 以下の整数
- $A_i$ は $0$ 以上 $15 \ 000$ 以下の整数
- $x_i$ は $1$ 以上 $N$ 以下の整数
- $v_i$ は $0$ 以上 $15 \ 000$ 以下の整数
入力
$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$
出力
$Q$ 行に渡って出力してください。
$i$ 行目には、$i$ 回目の操作が終わった後で部分和が $K$ となるようなものが存在する場合 $1$、そうでない場合 $0$ と出力してください。
サンプル
サンプル1
入力
3 8 4 4 9 3 1 4 2 5 3 3
出力
1 0 1
$1$ 回目の操作終了後の数列は $[4, 4, 9]$ です。$4 + 4 = 8$ という選び方が存在します。
$2$ 回目の操作終了後の数列は $[4, 5, 9]$ です。合計が $8$ となるような選び方は存在しません。
$3$ 回目の操作終了後の数列は $[4, 5, 3]$ です。$5 + 3 = 8$ という選び方が存在します。
サンプル2
入力
6 26 8 6 9 1 2 0 6 1 9 2 6 3 8 4 5 5 2 6 6
出力
1 1 1 0 0 1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。