009 - Brute Force 2 Editorial /

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000

注意

この問題は 2.4 節(計算量と全探索)と 3.7 節(動的計画法)両方で扱います。

全探索で解いても 1000 点中 500 点しか得られず、満点(AC)にならないことに注意してください。(本に記されている通り、一部の大きいケースでは現実的な時間で答えが求まらないからです)

問題文

N 枚のカードが横一列に並べられています。左から i 番目 (1 \leq i \leq N) のカードには整数 A_i が書かれています。

カードの中からいくつかを選んで、合計がちょうど S となるようにする方法はありますか。

制約

  • 1 \leq N \leq 60
  • 1 \leq A_i \leq 10000
  • 1 \leq S \leq 10000
  • 入力はすべて整数

部分点

  • 1 \leq N \leq 20 について解けると、500 点が獲得できます。

入力

入力は以下の形式で標準入力から与えられます。

N S
A_1 A_2 A_3 \dots A_N

出力

合計を S となるようにする方法が存在する場合は Yes、そうでない場合は No と出力してください。


入力例 1

3 11
2 5 9

出力例 1

Yes

カード 1, 3 を選べば合計が 11 になるので答えは Yes です。


入力例 2

4 11
3 1 4 5

出力例 2

No