salt_n_ice's blog

By salt_n_ice, history, 5 weeks ago, In English

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:

using namespace std;
#define ll long long
ll N =1e9+7;
int main()
    int n, x;
    int a[n];
    for(int i=0; i<n; ++i)
    ll cnt[x+1]={0};
    for(ll i=1; i<=x; ++i)
        for(ll j = 0; j<n; ++j)
            cnt[i] = (cnt[i]+cnt[i-a[j]])%N;

  • Vote: I like it
  • -2
  • Vote: I do not like it

5 weeks ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

make your mod constant.

const int mod = 1e9 + 7;

You are using long longs unnecessarily. (TLE with long longs) (AC with int)