Zero Remainder Sum

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
int mp[75][75];
int dp[75][75][75][75];

//dp[i][j][k][r]定义为：当前行选了k个，和能够余r的最大和 
//转移方程为：dp[i][j][k][r]如果不选第j个，dp[i][j][k][r] = dp[i][j-1][k][r]
//否则：dp[i][j][k][r] = dp[i][j-1][k-1][r-q]+a[i][j] （设a[i][j] % r = q） 
//行与行之间的关系可以通过dp[i+1][0][0][r] = max(dp[i][m][k][r])来转移
//最后答案是dp[n+1][0][0][0]

int main()
{
    int n, m, r;
    cin >> n >> m >> r;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> mp[i][j];
        }
    }
    memset(dp, -INF, sizeof(dp));
    dp[1][0][0][0] = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            for(int k = 0; k <= min(j, m/2); k++) {
                int q = mp[i][j] % r;
                for(int rr = 0; rr <= r-1; rr++) {
                    dp[i][j][k][rr] = dp[i][j-1][k][rr];
                    dp[i][j][k][rr] = max(dp[i][j][k][rr], dp[i][j-1][k-1][(rr - q + r) % r] + mp[i][j]); //q=a[i][j]%r 
                }
            }
        }

        for(int j = 0; j < r; j++) {
            for(int k = 0; k <= m / 2; k++) {
                dp[i + 1][0][0][j] = max(dp[i + 1][0][0][j], dp[i][m][k][j]);
            } 
        }
    }
    cout << dp[n + 1][0][0][0] << '\n';
}