最长题解

#include <iostream>//死装一下
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;
vector<long long> get_subset_sums(const vector<int>& arr) {
    vector<long long> sums = {0};
    for (int num : arr) {
        int size = sums.size();
        for (int i = 0; i < size; ++i) {
            sums.push_back(sums[i] + num);
        }
    }
    return sums;
}
int main() {
    int n, x;
    cin >> n >> x;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    int mid = n / 2;
    vector<int> left(a.begin(), a.begin() + mid);
    vector<int> right(a.begin() + mid, a.end());
    vector<long long> sum_left = get_subset_sums(left);
    vector<long long> sum_right = get_subset_sums(right);
    unordered_set<long long> mod_left_set;
    for (auto s : sum_left) {
        mod_left_set.insert(s % x);
    }
    unordered_set<long long> mod_right_set;
    for (auto s : sum_right) {
        mod_right_set.insert(s % x);
    }
    if (mod_left_set.count(x-1) || mod_right_set.count(x-1)) {
        cout << x-1 << endl;
        return 0;
    }
    bool found = false;
    for (long long a_mod : mod_left_set) {
        long long required = (x - 1 - a_mod + x) % x;
        if (mod_right_set.count(required)) {
            found = true;
            break;
        }
    }
    if (found) {
        cout << x-1 << endl;
        return 0;
    }
    vector<long long> sorted_right;
    long long max_right = 0;
    for (long long r : mod_right_set) {
        sorted_right.push_back(r);
        if (r > max_right) {
            max_right = r;
        }
    }
    sort(sorted_right.begin(), sorted_right.end());
    long long max_left = 0;
    for (long long m : mod_left_set) {
        if (m > max_left) {
            max_left = m;
        }
    }
    long long max_mod = max(max_left, max_right);
    for (long long a_mod : mod_left_set) {
        long long target = (x - 1 - a_mod);
        auto it = upper_bound(sorted_right.begin(), sorted_right.end(), target);
        if (it != sorted_right.begin()) {
            --it;
            long long candidate1 = a_mod + *it;
            if (candidate1 > max_mod) {
                max_mod = candidate1;
            }
        }
        long long candidate2 = (a_mod + max_right) % x;
        if (candidate2 > max_mod) {
            max_mod = candidate2;
        }
    }
    cout << max_mod << endl;
    return 0;
}