H - 3人の昼食 (The Lunch) Editorial /

Time Limit: 7 sec / Memory Limit: 600 MB

問題文

ある家には、square1001,E869120,うさぎの3人がいるが、その3人は昼食の値段の 差がああだこうだ、といってけんかが起きてしまう。

そこで、square1001は次のように言った。

「square1001とE869120の合計値段の差、square1001とうさぎの合計値段の差が 両方D以下になるようにしたいです。」

→2人は賛成した。

N個の食品があり、それらの値段はA_iである。また、E個までなら食品を残してもよい。

条件を満たす食品の分け方は何通りあるか。

入力

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

N D E
A_1
A_2
：
A_N
  • 1 行目には、整数 N, D, Eが空白区切りで与えられる。
  • 次のN 行には、整数 A_i が与えられる。

出力

食品の分け方の通り数を1行に出力せよ。

制約

  • 2≦N≦20
  • 0≦D≦1,000,000,000
  • 0≦E≦2
  • 1≦A_i≦1,000,000,000

部分点

この問題には、部分点が設定されている。

・2≦N≦10を満たすケースすべてに正解した場合は、20点が与えられる。

・11≦N≦20かつ条件を満たす食品の分け方が1000通り以下であるデータセットに正解した場合は、50点が与えられる。

・残りのデータセットすべてに正解した場合は、30点が与えられる。

入力例1

3 2 1
2
4
6

出力例1

4

square1001をA, E869120をB, うさぎをCとすると, 以下のように分けることができます。

食品1 食品2 食品3
方法1 A B ×
方法2 A C ×
方法3 B A C
方法4 C A B

入力例2

4 1 1
1
2
3
4

出力例2

10

問題文担当者：E869120