Why TLE? Can somebody figure this out?

Revision en2, by ProveMeRight, 2023-04-02 22:15:03

I was solving the CSES Dynamic Programming Problem named Coin Combinations I. I don't know what's the matter here.

In my view, Both the commented code, as well as uncommented code, is the same. But The uncommented code is throwing TLE and the Commented Code is passing all the test cases.

This is the code

vi dp(1000001, 0);
vi v(1000001, 0);
void solve() {
  int n, x;
  cin >> n >> x;
  FOR(i, 0, n) cin >> v[i];



  // for(int i =0;i<=x;i++)
  //   {
  //       // base case
  //       if(i==0)
  //       {
  //           dp[i] = 1;
  //       }
  //       else
  //       {   dp[i] = 0;
  //           for(int j = 0;j<n;j++)
  //           {
  //               if(i-v[j]>=0)
  //               dp[i] += dp[i-v[j]];
  //           }
  //           dp[i] %= mod;
  //       }
  //   }

  for(int i =0;i<=x;i++)
  {
    if (i == 0)
    {
      dp[i] = 1;
    }
    else
    {
      dp[i] = 0;
      for(int j = 0;j<n;j++)
      {
        if (i - v[j] >= 0)
        {
          dp[i] += dp[i - v[j]];
        }
        dp[i] %= mod;
      }
    }
  }

  cout << dp[x] << endl;
}

Please Help Me. Thank you.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English ProveMeRight 2023-04-02 22:15:03 848
en1 English ProveMeRight 2023-04-02 22:12:31 457 Initial revision (published)