F - Team Making
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
QUPC 2022 九州大学オンサイトには N 人の参加者がいます。i 番目の参加者の AtCoder のレーティングは A_i です。
N 人の参加者を以下の条件を満たすように、いくつかのチームに分けます。
- 各チームの人数は 1 人以上 3 人以下
- 各チームに所属する参加者の AtCoder のレーティングの平均値は K 以下
- AtCoder のレーティングの値に関わらず、1 人チームとして参加することは可能
条件を満たすチームの分け方は何通りあるかを求めてください。この問題の制約下で、答えは 10^{18} を超えないことが保証されています。
制約
- 1 \leq N \leq 18
- 0 \leq K \leq 4208
- 0 \leq A_i \leq 4208
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 ... A_N
出力
条件を満たすチームの組み方の個数を出力してください。
入力例 1
3 2000 1999 2000 2001
出力例 1
4
3 人以下のチームの組み方は以下の 5 通りで、上の 4 通りが条件を満たします。
- 1 番目の参加者単独のチーム、2 番目の参加者単独のチーム、3 番目の参加者単独のチーム
- 1 番目の参加者と 2 番目の参加者と 3 番目の参加者の 3人チーム
- 1 番目の参加者と 2 番目の参加者の 2 人チーム、3 番目の参加者単独のチーム
- 1 番目の参加者と 3 番目の参加者の 2 人チーム、2 番目の参加者単独のチーム
- 2 番目の参加者と 3 番目の参加者の 2 人チーム、1 番目の参加者単独のチーム
入力例 2
4 2000 2500 3000 1000 2000
出力例 2
6
入力例 3
12 2000 3092 2432 2312 1867 1794 1730 1670 1523 1495 1299 1169 1024
出力例 3
297042