Josif_tepe

Untitled

Jul 21st, 2025
337
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.67 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstring>
  3. using namespace std;
  4. typedef long long ll;
  5. const int maxn = 105;
  6. int n, m, k;
  7. ll dp[maxn][maxn];
  8. ll rec(int food, int rooms) {
  9.     if(food == n and rooms == k) {
  10.         return 1;
  11.     }
  12.    
  13.     if(dp[food][rooms] != -1) {
  14.         return dp[food][rooms];
  15.     }
  16.     ll res = 0;
  17.     for(int i = 1; i <= m; i++) {
  18.         if(food + i <= n) {
  19.             res += rec(food + i, rooms + 1);
  20.         }
  21.     }
  22.    
  23.     dp[food][rooms] = res;
  24.     return res;
  25. }
  26. int main() {
  27.     ios_base::sync_with_stdio(false);
  28.     memset(dp, -1, sizeof dp);
  29.     cin >> n >> k >> m;
  30.    
  31.     cout << rec(0, 0) << endl;
  32.    
  33.     return 0;
  34. }
  35.  
Advertisement
Add Comment
Please, Sign In to add comment