I am trying to solve this problem http://www.spoj.com/problems/NUMTSN/ on spoj. I tried to use dynamic programming. I am getting TLE. Here is my code: http://ideone.com/VnPIZp \ //

int dp[54][2][18][18][18];

int solve(int index, int free, int t,int s, int n) { if(t > 17 || s > 17 || n > 17) return 0;

//DBG(index);
if(index == num)
{
    //DBG(index);
    if(t >= 1 && (t == s) && (s == n))
     return 1;
    return 0;
}
int &ret = dp[index][free][t][s][n];
if(ret != -1) return ret;
ret = 0;
int nfree,nt,ns,nn;
for(int i = 0; i < 10; i++)
{
    nfree = free | (i < a[index]);
    nt = t + ( (i == 3) ? 1 : 0); //DBG(nt);
    ns = s + ( (i == 6) ? 1 : 0); //DBG(ns);
    nn = n + ( (i == 9) ? 1 : 0); //DBG(nn);
    if(free)
    {
       ret = ((ret % MOD) + (solve(index+1, nfree, nt, ns, nn)) % MOD) % MOD;
    }
    else
    {
       if( i <= a[index])
        ret = (ret % MOD +   (solve(index+1, nfree, nt, ns, nn)) % MOD ) % MOD;
    }

}

return (ret% MOD);

}