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:

#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];
}

 
 
 
 
  • 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.

https://codeforces.com/contest/1433/submission/96206083 (TLE with long longs)

https://codeforces.com/contest/1433/submission/96206062 (AC with int)