本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-17 14:11:14

本题是要求序列中的 $\max \sum\limits_{i=0}^{\lvert x\rvert -1 } A_{x_i} \le T$。

注意到 $N \le 40$，无法直接进行子集枚举。但是如果我们将其分为两半，那么 $N' \le 20$，这时进行子集枚举可行。

于是我们就在 $A =T_1, \cdots, T_{\lfloor N/2\rfloor}$ 与 $B =T_{\lceil N/2\rceil}, \cdots, T_N$ 上进行子集枚举，求出每种状态的和。

最后，我们将两个子问题的解组合在一起：在其中一个子集上进行遍历：对 $A_i$，我们需要找到一个 $B_j$ 使得 $A_i + B_j$ 最大且小于等于 $T$。

这就是 upper_bound 的上一个元素。用指针就是 upper_bound (...)[-1]。取最大值即可。

源代码