communication-easy

2 secs 1024 MB
Ang107's icon Ang107
Tweet
Problem
Submissions
Test cases
Editorial

問題文

注: この問題は「communication-hard」とほぼ同じ設定です。本文中で太字で示されている部分および制約のみが異なります。

あなたは、とある「アイドルプロデュース体験ゲーム」を遊んでいます。

このゲームでは、担当しているアイドルと「コミュニケーション」を取ることができます。
「コミュニケーション」には NN 回の選択パートが存在し、各パートでは次のような行動を行います。

  • ii 回目のパートでは Ki (1≤i≤N)K_i \, (1 \leq i \leq N) 個の選択肢が提示される。
  • その中から j (1≤j≤Ki)j \, (1 \leq j \leq K_i) 番目の選択肢を選んだ場合、コミュニケーションポイントに Si,jS_{i,j} が加算される。
    • Si,jS_{i,j} は整数であり、負の値を取ることもある。
    • 各選択の効果は独立しており、過去の選択に依存しない。
    • KiK_i 個のうち、いずれかの選択肢を必ず選ばなければならない。

はじめ、コミュニケーションポイントは 00 です。
すべての選択を終えた後、最終的なコミュニケーションポイントが XX 以上であれば「パーフェクトコミュニケーション」となります。

選択の総数は ∏i=1NKi\prod_{i=1}^{N} K_i 通りありますが、そのうち「パーフェクトコミュニケーション」となる選び方が何通りあるかを求めてください。

制約

  • 1≤N≤101 \leq N \leq 10
  • −109≤X≤109-10^9\leq X \leq 10^9
  • 2≤Ki≤4 (1≤i≤N)2 \leq K_i \leq 4\, (1 \leq i \leq N)
  • −108≤Si,j≤108 (1≤i≤N,1≤j≤Ki)-10^8 \leq S_{i,j} \leq 10^8\, (1 \leq i \leq N, 1 \leq j \leq K_i)
  • 入力はすべて整数

入力

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

NN XX
K1K_1 S1,1S_{1, 1} S1,2S_{1, 2} …\dots S1,K1S_{1, K_1}
K2K_2 S2,1S_{2, 1} S2,2S_{2, 2} …\dots S2,K2S_{2, K_2}
.
.
.
KNK_N SN,1S_{N, 1} SN,2S_{N, 2} …\dots SN,KNS_{N, K_N}

出力

「パーフェクトコミュニケーション」となる選び方が何通りあるかを出力してください。

入力例 1

2 3
2 1 3
3 -10 2 0

出力例 1

3

最終的にコミュニケーションポイントが 33 以上となるような選び方は、(S1,1,S2,2),(S1,2,S2,2),(S1,2,S2,3)(S_{1, 1}, S_{2, 2}), (S_{1, 2}, S_{2, 2}), (S_{1, 2}, S_{2, 3}) の 33 通りだけです。
よって 33 を出力します。

入力例 2

2 3900
3 765 961 100
4 876 346 315 283

出力例 2

0

「パーフェクトコミュニケーション」となる選び方が存在しない場合もあります。

入力例 3

2 -3900
3 765 961 100
4 876 346 315 283

出力例 3

12

Submit

Go (1.21)