Problem: https://codeforces.me/problemset/problem/431/C
I started solving this one by thinking a $$$DP[sum][level]$$$ state, which means ways to achieve a given sum on a given level, and the maximum number occurring in the sum. And, I coded its recurrence similar to subset sum as,
vector<vector<pair<ll,ll>>> dp(n+1, vector<pair<ll,ll>>(n+1, { 0, 0 }));
// dp[i][l]: sum i at level l, { ways, max }
dp[0][0] = { 1, 0 };
for(ll i = 1; i <= n; i++) { // level
for(ll j = 1; j <= k; j++) { // number
for(ll s = n; s-j >= 0; s--) { // sum
if(dp[s-j][i-1].first > 0) {
// j is added to s-j sum from prev level, making a sum of s in the curr level
dp[s][i].first = (dp[s][i].first + dp[s-j][i-1].first) % M;
// adjusting the max of curr level with j
dp[s][i].second = max(j, dp[s-j][i-1].second);
}
}
}
}
And, after computing the required DP states, I am adding the ways of making sum $$$n$$$ from each level $$$i$$$, when $$$max >= d$$$ as,
ll ans = 0;
for(ll i = 1; i <= n; i++) {
if(dp[n][i].second >= d) ans = (ans + dp[n][i].first) % M;
}
cout << ans;
For some reasons, this is giving wrong answer verdict on test 5, can anyone kindly explain me why it is incorrect and how to improve it?
Submission link: https://codeforces.me/contest/431/submission/138596746