Help! its a CSES DP problem

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:


using namespace std;
// #define int long long
int INF = 1e9+7;
signed main()

    int 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++)
    return 0;

Your help will be appreciated.

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

It still showing tle :smiling_face_with_tear:

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

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

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

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