this is a classic dp problem, very similar to the knapsack problem. the DP's state will be the current column, row, how many numbers we picked in the current row and the mod of the current sum.
| 20 | // the DP's state will be the current column, row, how many numbers we picked |
| 21 | // in the current row and the mod of the current sum. |
| 22 | int solve(int a, int b, int left, int mod) { |
| 23 | // if we have already visited the current state we just return it's value. |
| 24 | if(dp[a][b][left][mod]!=-1) return dp[a][b][left][mod]; |
| 25 | |
| 26 | // we have three transitions: |
| 27 | // we can pick an element, not pick an element, |
| 28 | // and transition from one row to the next |
| 29 | int ans; |
| 30 | if(a == n) { |
| 31 | // the answer will be mod 0. |
| 32 | if(mod == 0) return 0; |
| 33 | // we don't want the other mods. |
| 34 | else return -inf; |
| 35 | } |
| 36 | // transision from one row to the next |
| 37 | else if(b == m) ans = solve(a+1,0,T,mod); |
| 38 | // don't pick the current element and move to the next column |
| 39 | else if(left == 0) ans = solve(a,b+1,left,mod); |
| 40 | else { |
| 41 | // pick the current element |
| 42 | int x = mat[a][b] + solve(a,b+1,left-1,(mod+mat[a][b])%k); |
| 43 | // don't pick the current element and move to the next column |
| 44 | int y = solve(a,b+1,left,mod); |
| 45 | |
| 46 | // store and return the maximum, because we want to maximize. |
| 47 | return dp[a][b][left][mod] = max(x,y); |
| 48 | } |
| 49 | |
| 50 | // storing the current state's value. |
| 51 | return dp[a][b][left][mod] = ans; |
| 52 | } |
| 53 | |
| 54 | int main() { |
| 55 | scanf("%d%d%d",&n,&m,&k); |