Codeforces 888E - Maximum Subsequence（折半枚举（meet-in-the-middle））

888E - Maximum Subsequence

思路：折半枚举。

代码：

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define pb push_back

#define mem(a,b) memset(a,b,sizeof(a))

const int N=;

int a[N];

set<int>s;

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

    int n,m;

    cin>>n>>m;

    for(int i=;i<n;i++)cin>>a[i],a[i]=a[i]%m;

    sort(a,a+n);

    int hf=n/;

    int _hf=n-hf;

    for(int i=;i<(<<hf);i++)

    {

        int t=;

        for(int j=;j<hf;j++)if((<<j)&i)t=(t+a[j])%m;

        s.insert(t);

    }

    set<int>::iterator it;

    int ans=;

    for(int i=;i<(<<_hf);i++)

    {

        int t=;

        for(int j=;j<_hf;j++)if((<<j)&i)t=(t+a[j+hf])%m;

        it=s.upper_bound(m--t);

        if(it==s.begin())

        {

            ans=max(ans,t);

            continue;

        }

        it--;

        ans=max(ans,t+*it);

    }

    cout<<ans<<endl;

    return ;

}