CSES Coins Combinations II TLE

Debugging Help
#1

Hey people,

I was solving the CSES dp problemset and I am genuinely at a loss for why I got TLE for some testcases.

#include <bits/stdc++.h>
using namespace std; 
typedef long long ll;
ll mod = 1e9+7;
#define rep(i, n) for(ll i = 0, _n = (ll)(n); i < _n; i++)
#define vci vector<int>
int main(){
  int n,k;
  cin >> n >> k;
  vci arr(n);
  rep(i,n) cin >> arr[i];
  vector<ll> dp(k+1,0);
  dp[0]=1;
  rep(i,k) dp[i+1]=0;
  rep(j,n){
    for(int i = arr[j];i<=k;i++) {
      if(i>=arr[j]){
        dp[i]=(dp[i]+dp[i-arr[j]])%mod;
      }
    }
  }
  cout << dp[k]<< endl;
}

The code is near identical to the solution provided in the USACO guide so I would really like to know where the fault lies.
Any help would be seriously appreciated.

1 Like
#2

try switching ll to int?

the time limit for this problem is rather tight

1 Like
#3

Thanks! switching the vector and ll mod to int seems to do the trick.

1 Like