CCCPaste

152c4e8acc302

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn = 105;
int food, rooms, max_cap;

ll dp[maxn][maxn];
ll rec(int at_food, int room_cnt) {
if(at_food == food and room_cnt == rooms) {
return 1;
}

if(dp[at_food][room_cnt] != -1) {
return dp[at_food][room_cnt];
}

ll res = 0;
for(int i = 1; i <= max_cap; i++) {
if(at_food + i <= food) {
res += rec(at_food + i, room_cnt + 1);
}
}

dp[at_food][room_cnt] = res;
return res;
}
int main() {
ios_base::sync_with_stdio(false);
cin >> food >> rooms >> max_cap;
memset(dp, -1, sizeof dp);
cout << rec(0, 0) << endl;
return 0;
}