Advertisement
deushiro

Untitled

Dec 18th, 2019
178
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.95 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. int n;
  8.  
  9. int main() {
  10.     ios_base::sync_with_stdio(false);
  11.     cin.tie(0);
  12.     cout.tie(0);
  13.     int n, k;
  14.     cin >> n >> k;
  15.     vector<vector<int>> u(n, vector<int> (n));
  16.     vector<vector<int>> d(n, vector<int> (n));
  17.     d[k - 1][k - 1] = 1;
  18.     u[k - 1][k - 1] = 1;
  19.     for(int i = k; i < n; ++i){
  20.         u[k - 1][i] = 1;
  21.         d[k - 1][i] = 1;
  22.     }
  23.     for(int i = k + 1; i < n; ++i){
  24.         u[i][0] = 0;
  25.         d[i][0] = u[i - 1][n - 1];
  26.         for(int j = 1; j < n; ++j){
  27.             if(i - j < k - 1){
  28.                 d[i][j] = d[i][j - 1];
  29.                 u[i][j] = u[i][j - 1];
  30.             }
  31.             else{
  32.                 u[i][j] = d[i - j - 1][j - 1] + u[i][j - 1];
  33.                 d[i][j] = d[i - j - 1][n - 1] - d[i - j - 1][j] + d[i][j - 1];
  34.             }
  35.         }
  36.  
  37.     }
  38.     cout << d[n - 1][n - 1] + u[n - 1][n - 1] << "\n";
  39.  
  40.  
  41. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement