I need help in problem: Codeforces 431C — k-Tree

Revision en1, by shisukenohara, 2024-10-07 16:41:32

I am new at CP, and have only given one contest Can someone please help me and tell me what is wrong in my approach for the question 431C - k-Tree. I am trying Dynamic Programming.

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double

const int MOD = 1000000007;
vector<vector<int>> memo;

int dp(int k, int n, int d, int found)
{
  if(n==0)
  {
    if(found) return 1;
    else return 0;
  }
  if(n<0)
  {
    return 0;
  }
  if(memo[n][found]!=-1)
  {
    return memo[n][found];
  }
  int total = 0;
  for(int i=1; i<=k; i++)
  {
    if(n-i < 0) break;
    total = (total%MOD + dp(k, n-i, d, found || i>=d)%MOD)%MOD;
  }
  return memo[n][found] = total%MOD;
  
}

int32_t main() 
{
  int k, n, d;
  cin >> k >> n >> d;
  memo = vector<vector<int>>(n+1, vector<int>(2, -1));
  cout << dp(k, n, d, 0) << "\n";
  return 0;
}

Fails on Test case 5: 4 3 2

Expected: 6

Output: 3

Tags dp, trees, implementation, *1600, help, memoization, c++, new

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English shisukenohara 2024-10-07 16:41:32 1045 Initial revision (published)