题解

#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
vector<int> a(n);
for(int i=0;i<n;i++){
cin>>a[i];
}
int n1=n/2,n2=n-n1;
vector<int> l,r;
for(int ms=0;ms<(1<<n1);ms++){
long long s=0;
for(int i=0;i<n1;i++){
if(ms>> i & 1) s+=a[i];
}
l.push_back(s%m);
}
for(int ms=0;ms<(1<<n2);ms++){
long long s=0;
for(int i=0;i<n2;i++){
if(ms>> i & 1) s+=a[n1+i];
}
r.push_back(s%m);
}
sort(l.begin(),l.end());
int ans=0;
if(!l.empty()) ans=max(ans,l.back());
for(int y:r) ans=max(ans,y);
for(int y:r){
int ne=m-y;
auto it=lower_bound(l.begin(),l.end(),ne);
if(it!=l.begin()){
--it;
ans=max(ans,(*it+y)%m);
}
if(!l.empty()){
int xm=l.back();
ans=max(ans,(xm+y)%m);
}
}
cout<<ans;
return 0;
}