SMMR-T102: Combinato

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ulli;

const int N = 100;
const int X = 1e4;

int board[N + 1][N + 1];
ulli dp[X + 1][N + 1][N + 1];

int main(){

    int row, col, Q;
    scanf("%d%d%d", &row, &col, &Q);
    for(int i = 1; i <= row; ++i){
        for(int j = 1; j <= col; ++j){
            scanf("%d", &board[i][j]);
        }
    }
    int curr = 0;
    for(int i = 1; i <= row; ++i){
        if(curr + board[i][1] <= X){
            dp[curr + board[i][1]][i][1] = 1;
        }
        curr += board[i][1];
    }
    curr = 0;
    for(int j = 1; j <= col; ++j){
        if(curr + board[1][j] <= X){
            dp[curr + board[1][j]][1][j] = 1;
        }
        curr += board[1][j];
    }
    for(int i = 2; i <= row; ++i){
        for(int j = 2; j <= col; ++j){
            for(int x = 1; x <= X; ++x){
                dp[x][i][j] = 0;
                if(x >= board[i][j]){
                    dp[x][i][j] = dp[x - board[i][j]][i - 1][j] + dp[x - board[i][j]][i][j - 1];
                }
            }
        }
    }
    while(Q--){
        int x;
        scanf("%d", &x);
        if(x <= 0){
            cout << "0\n";
            continue;
        }
        cout << dp[x][row][col] << '\n';
    }

    return 0;
}