Josif_tepe

Untitled

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