不使用库的解法
C++ 代码
#include <iostream>
using namespace std;
int m, n;
unsigned long long a[40];
class mVector{
public:
mVector()
{
data = new int[2];
maxLen = 2;
}
~mVector()
{
delete[] data;
}
void push(int a)
{
if (len + 1 > maxLen)
{
int* oldData = data;
maxLen *= 2;
data = new int[maxLen];
for (int i = 0; i < len; ++i)
{
data[i] = oldData[i];
}
delete[] oldData;
}
data[len++] = a;
}
int* data = {};
int len = {};
int maxLen = {};
};
void quick_sort(int q[], int l, int r){
if (l >= r) return;
int i = l - 1, j = r + 1, x = q[(l + r) / 2];
while (i < j){
while (q[++i]<x);
while (q[--j]>x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
}
void dfs(int start, int end, int sum, mVector &mods){
mods.push(sum%m);
for (int i = start; i < end; i++){
dfs(i + 1, end, sum + a[i], mods);
}
}
int mMax(int a, int b){
return a>b ? a : b;
}
int main(){
cin >> n >> m;
for (int i = 0; i < n; i++){
cin >> a[i];
}
mVector l, r;
dfs(0, n / 2, 0, l);
dfs(n / 2, n, 0, r);
quick_sort(l.data, 0, l.len-1);
quick_sort(r.data, 0, r.len-1);
int res = (l.data[l.len - 1] + r.data[r.len - 1]) % m;
for (int i = 0, j = r.len - 1; i<l.len; i++)
{
while (j >= 0 && l.data[i] + r.data[j] >= m) j--;
if (j >= 0) res = mMax(res, (l.data[i] + r.data[j]) % m);
}
cout << res << endl;
return 0;
}