P16016 [ICPC 2021 NAC] Contest Construction

ICPC NAC 的工作人员已经编写了许多题目，并希望从中挑选若干道组成一套试题。每道题都有一个正整数的难度值。 如果一套试题的难度值按升序排序后，从第三道题开始，每一道题的难度值都不大于其前面两道题的难度值之和，则称该套试题具有 **优美** 的难度分布。 给定若干道题目的难度值，以及希望组成的试题数量，请计算可以构成的具有优美难度分布的试题集的数量。两个试题集被视为不同，当且仅当存在一道题目属于其中一个试题集而不属于另一个试题集。（特别地，需要注意，即使题目顺序不同，只要所含题目相同，就视为同一个试题集。）

输入的第一行包含两个整数 $n$（$3 \le n \le 50$）和 $k$（$3 \le k \le 18$，$k \le n$），其中 $n$ 表示工作人员已编写的题目总数，$k$ 表示他们希望放入试题集的题目数量。 接下来的 $n$ 行，每行包含一个整数 $d$（$1 \le d \le 10^9$），表示每道题目的难度值。

输出一个整数，表示可以构成的具有优美难度分布的试题集的数量。

翻译由 DeepSeek V3.2 完成