题解 | 小红取数

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;

    vector<long long> dp(k, -1);
    // 注意：不初始化 dp[0] 为 0，因为空集不算有效选择

    for (int i = 0; i < n; ++i) {
        long long x;
        cin >> x;

        vector<long long> next_dp(dp);

        // 从已有状态更新
        for (int r = 0; r < k; ++r) {
            if (dp[r] != -1) {
                int new_r = (r + x % k) % k;
                next_dp[new_r] = max(next_dp[new_r], dp[r] + x);
            }
        }

        // 当前数可以单独成为起点
        int r = x % k;
        next_dp[r] = max(next_dp[r], x);

        dp = next_dp;
    }

    // 修复点：dp[0] == 0 表示“只选了空集”，也不合法！
    if (dp[0] <= 0) cout << -1 << endl;
    else cout << dp[0] << endl;

    return 0;
}