标题：正如标题所示
当n=35时。爆搜的复杂度是$O(2^n)$,肯定是不能接受的，这时候就可以用折半搜索了。
折半搜索的思想是：先搜一半数据的答案，在搜另一半数据的答案，最后合并这两个答案，得到最终的答案。
例如此题:Maximum Subsequence
可以先爆搜搜出前半段的答案，再搜出后半段的答案，得到两个序列$ans1,ans2$， 设最终的答案是$ans$
对$ans1,ans2$进行排序，现在要做的就是把两个序列中取两个数，让他们加起来摸m的值最大即可，这要利用双指针。
对于一个$ans1中的i$来说，$ans2序列可以分为两个部分：1.ans1[i]+ans2[j]>=m,2.ans1[i]+ans2[j]<m$那么谁会贡献答案呢？
对于1来说，每个j都可能贡献答案，对于2来说，只有最大的那一个才会贡献答案。
当i++时，j不需要从头再来，（下次再说）
code:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m, k;
int a[100], ans;
vector<int> ans1, ans2;
void dfs1(int i, int sum) {
if(i == k + 1) {
ans1.push_back(sum);
return;
}
dfs1(i + 1, sum);
dfs1(i + 1, (sum + a[i]) % m);
}
void dfs2(int i, int sum) {
if(i == n + 1) {
ans2.push_back(sum);
return;
}
dfs2(i + 1, sum);
dfs2(i + 1, (sum + a[i]) % m);
}
int main() {
cin >> n >> m;
for(int i = 1 ; i <= n ; i ++) {
cin >> a[i];
a[i] %= m;
}
k = n / 2;
dfs1(1, 0);
dfs2(k + 1, 0);
int l1 = ans1.size(), l2 = ans2.size();
sort(ans1.begin(), ans1.end());
sort(ans2.begin(), ans2.end());
int j = l2 - 1;
for(int i = 0 ; i < l1 ; i ++) {
while(j >= 0 && ans1[i] + ans2[j] >= m) {
ans = max(ans, (ans1[i] + ans2[j]) % m);
j --;
}
if(j < 0) break;
ans = max(ans, ans1[i] + ans2[j]);
}
cout << ans;
}