888E - Maximum Subsequence - CodeForces Solution

// https://codeforces.com/contest/888/problem/E

#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;

int n, m;   // n <= 35
int a[40];  
vector<int> ml, mr;
int ans;

void generate(int l, int r, vector<int> &res) {
    for (int bm = 0; bm < (1 << (r-l+1)); bm++) {
        int sum = 0;
        for (int i = 0; i < r-l+1; i++) {
            if (bm & (1 << i)) 
                sum = (sum + a[l+i]) % m;
        }
        res.push_back(sum);
    }
    sort(res.begin(), res.end());
    res.resize(unique(res.begin(), res.end()) - res.begin());
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    generate(0, n/2, ml);
    generate(n/2+1, n-1, mr);
    ans = max(ml.back(), mr.back());
    for (int x: ml) {
        auto it = lower_bound(mr.begin(), mr.end(), m-1-x);
        if (it != mr.end() && *it == m-1-x) {
            printf("%d", m-1); return 0;
        }
        if (it == mr.end() || *it > m-1-x && it != mr.begin()) {
            it--;
            ans = max(ans, x + *it);
        }
        // 对于x+y > m，这个一定不如单选x(或y)好，因为(x+y) % m < x
        // ans = max(ans, (x + mr.back()) % m);
    }
    printf("%d\n", ans);

    return 0;
}