F. Zero Remainder Sum

dp

 

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 73;

int a[maxn][maxn], dp[maxn][maxn][maxn][maxn], d[maxn][maxn];

int main()
{
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            scanf("%d", &a[i][j]);
    memset(dp, -1, sizeof(dp));
    memset(d, -1, sizeof(d));
    for(int i = 1; i <= n; ++i) dp[i][0][0][0] = 0;
    for(int i = 1; i <= n; ++i)//第i行
    {
        for(int j = 0; j < m; ++j)//考虑到第j+1个数是否取
        {
            for(int k1 = 0; k1 <= m/2; ++k1)//取k1个数
            {
                for(int k2 = 0; k2 < k; ++k2)//sum%k等于k2
                {
                    if(dp[i][j][k1][k2] == -1) continue;
                    dp[i][j+1][k1][k2] = max(dp[i][j][k1][k2], dp[i][j+1][k1][k2]);
                    dp[i][j+1][k1+1][(k2+a[i][j+1])%k] = max(dp[i][j][k1][k2] + a[i][j+1], dp[i][j+1][k1+1][(k2+a[i][j+1])%k]);
                }
            }
        }
    }
    d[0][0] = 0;
    dp[0][m][0][0] = 0;
    for(int i = 0; i < n; ++i)//前i行
    {
        for(int j = 0; j < k; j++)//sum%k等于j
        {
            for(int k1 = 0; k1 <= m / 2; k1++)
            {
                for(int k2 = 0; k2 < k; k2++)
                {
                    if(d[i][j] == -1) continue;
                    if(dp[i+1][m][k1][k2] == -1) continue;
                    d[i+1][(j+k2)%k] = max(d[i][j] + dp[i+1][m][k1][k2], d[i+1][(j+k2)%k]);
                }
            }
        }
    }
    printf("%d\n", d[n][0]);
    return 0;
}