mickypinata

SMMR-T102: Combinato

Jul 27th, 2021
847
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef unsigned long long ulli;
  5.  
  6. const int N = 100;
  7. const int X = 1e4;
  8.  
  9. int board[N + 1][N + 1];
  10. ulli dp[X + 1][N + 1][N + 1];
  11.  
  12. int main(){
  13.  
  14.     int row, col, Q;
  15.     scanf("%d%d%d", &row, &col, &Q);
  16.     for(int i = 1; i <= row; ++i){
  17.         for(int j = 1; j <= col; ++j){
  18.             scanf("%d", &board[i][j]);
  19.         }
  20.     }
  21.     int curr = 0;
  22.     for(int i = 1; i <= row; ++i){
  23.         if(curr + board[i][1] <= X){
  24.             dp[curr + board[i][1]][i][1] = 1;
  25.         }
  26.         curr += board[i][1];
  27.     }
  28.     curr = 0;
  29.     for(int j = 1; j <= col; ++j){
  30.         if(curr + board[1][j] <= X){
  31.             dp[curr + board[1][j]][1][j] = 1;
  32.         }
  33.         curr += board[1][j];
  34.     }
  35.     for(int i = 2; i <= row; ++i){
  36.         for(int j = 2; j <= col; ++j){
  37.             for(int x = 1; x <= X; ++x){
  38.                 dp[x][i][j] = 0;
  39.                 if(x >= board[i][j]){
  40.                     dp[x][i][j] = dp[x - board[i][j]][i - 1][j] + dp[x - board[i][j]][i][j - 1];
  41.                 }
  42.             }
  43.         }
  44.     }
  45.     while(Q--){
  46.         int x;
  47.         scanf("%d", &x);
  48.         if(x <= 0){
  49.             cout << "0\n";
  50.             continue;
  51.         }
  52.         cout << dp[x][row][col] << '\n';
  53.     }
  54.  
  55.     return 0;
  56. }
  57.  
RAW Paste Data