Help! its a CSES DP problem

help
, ,
1

Hey there!! I am stuck in this problem for quit some time, can you guys can please help me…
It is CSES DP coin combination( CSES - Coin Combinations I ) , It results in TLE in 3 test cases.
my code:

#include<bits/stdc++.h>

using namespace std;
// #define int long long
int INF = 1e9+7;
 
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n , m ;
    cin>>n>>m;
 
    vector<int> a(n);
 
    for(int i = 0;i<n;i++) cin>>a[i];
 
    vector<int> c(m+1,0);
 
    c[0] = 1;
    
 
    for(int i = 1;i<=m;i++) 
        for(int j = 0;j<n;j++)
        {
            if(i-a[j]>=0)
            {
                c[i]=(c[i]+c[i-a[j]])%INF;
            }
        }
    
    cout<<c[m]%INF<<'\n';
    
 
    return 0;
}

Your help will be appreciated.

2

Do, c[i]+=(c[i-a[j]]%mod);

And read a article about cache misses, I guess there is one on codeforces about it

1 Like
4

It still showing tle :smiling_face_with_tear:

5

if(i>=a[j]) ? In place of subtracting if(i-a[j])>=0. This question’s constraints are too tight. The answer is right most certainly, you shouldn’t bother too much.

1 Like
6

it still not working, I checked out some accepted solution but they are same as mine ,but thanks a lot for your efforts.

7

Have you tried using memoization?? It might reduce time because some operations will be precomputed.

8

Try sorting the array and then when a[j] becomes greater than i breakout of the inner for loop, maybe this can improve the runtime