### salt_n_ice's blog

By salt_n_ice, history, 5 weeks ago,

This is the problem I am talking about, although this has happened with some other problems as well. The solution is straightforward using dp, but I was getting TLE for 2 test cases, and the time complexity was O(n*x) so I thought some optimization was required, so I then looked at his stream and he did exactly the same as me, Only minor differences, which I changed in my solution to make it look exactly like him. But Still! It's still showing TLE while his was accepted! Here is the solution:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll N =1e9+7;
int main()
{
int n, x;
cin>>n>>x;
int a[n];
for(int i=0; i<n; ++i)
{
cin>>a[i];
}
ll cnt[x+1]={0};
cnt[0]=1;
for(ll i=1; i<=x; ++i)
{
for(ll j = 0; j<n; ++j)
{
if(i>=a[j])
cnt[i] = (cnt[i]+cnt[i-a[j]])%N;
}
}
cout<<cnt[x];
}



• -2

 » 5 weeks ago, # | ← Rev. 2 →   +10 make your mod constant.const int mod = 1e9 + 7;You are using long longs unnecessarily.https://codeforces.com/contest/1433/submission/96206083 (TLE with long longs)