No.043 B

問題は難易度の昇順でソートしておく.

$i$ 番目の問題まで見たときに $j$ 問選ぶ組み合わせの数を $C(i, j)$ とすると,

$$C(i, j) = C(i-1, j) + C(i-1, k)$$

となる. ただし, $k$ は $D_k \leq D_i/2$ を満たす最大の $k$ である. このような $k$ は二分探索で求めることができる.

この $C(i, j)$ を DP で計算して, $C(N, 4)$ を見ればいい.