Help in CSES Coin-Combination II

help
,
1

I am getting TLE in this problem,

Here is a link to my code : csesCode
Problem Link

#include<iostream>
#include<vector>
#define ll long long
ll mod = 1e9+7;
using namespace std;
 
int main(){
    ll n,k;
    cin>>n>>k;
 
    ll *a = new ll[n];
 
    for(ll i = 0;i<n;i++){
        cin>>a[i];
    }
 
    vector<ll> dp(k+1,0);
    dp[0] = 1;
 
    for(ll i = 0;i<n;i++){
        for(ll j = 1;j<=k;j++){
            if((j- a[i])>=0){
                dp[j] = (dp[j] + dp[j-a[i]]);
                dp[j]%=mod;
            }
        }
    }
 
    cout<<dp[k];
    return 0;
}
2

Here are some points I have:

  • Always compute the modulo on the operation, not after it. So your 23rd line should be:
     dp[j] = (dp[j] + dp[j-a[i]]) % mod;
  • Your complexity is O(n*k), which is O(108). You can try using fast input methods such as:
     std::ios_base::sync_with_stdio(false);
     cin.tie(0);