思路

三维的0-1背包，$dp[i][j]$状态表示选了j个数且和为i的三数之和最大值方案，状态转移方程为$dp[i][j] = max(val + dp[i - w][j - 1], dp[i][j])$，其中val为枚举物品的价值，w为所占的空间，由$(a[i] + a[j] + a[l]) % k = 0$得$((a[i] \% k) + (a[j] \% k) + a[l] \% k)) \% k = 0$
所以我们先将数组中的数对k取模，再贪心地维护每一个取模后的数对应取模前最大的三个数。所以我们可以保证所有数的数量不超过3k, 三数之和的大小不超过3k，接下来就放心地做0-1背包就好了~

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N = 1e5 + 5;
int a[N], dp[3005][4], val[1005];
//dp[i][j]表示选了j个数且和为i的最大方案
//对序列中每一个元素对k取模，对取模后的每一个数所对应的原来的值做个排序，取前三大，时间复杂度是O((k^2)log(k))
//这些数规模最大不超过3k,同时三数之和的大小不超过3k，做一个0-1背包，时间复杂度是O(3k*3k*3)
int main()
{
    int n, k;
    cin >> n >> k;
    memset(dp, -1, sizeof(dp));
    vector<vector<int>> v(k, vector<int>());
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        v[a[i] % k].push_back(a[i]);
    }
    vector<pair<int, int>> mp;
    for(int i = 0;i < k;i++) {
        if(v[i].size()) sort(v[i].begin(), v[i].end(), greater<int>());
        for(int j = 0;j < 3 && j < v[i].size();j++) {
            mp.push_back({i, v[i][j]});
        }
    }
    int ans = 0;
    dp[0][0] = 0;
    for(auto i : mp) {
        for (int j = 3 * k; j >= i.first; j--) {
            for (int m = 3; m >= 1; m--) {
                if (dp[j - i.first][m - 1] != -1) {
                    dp[j][m] = max(i.second + dp[j - i.first][m - 1], dp[j][m]);
                }
            }
            if (j % k == 0) ans = max(ans, dp[j][3]);
        }
    }
    cout << ans << endl;
    return 0;
}