I have written a solution with O(n * (m + h) + k * h * h * n * (m + h)) time and O(n * (m + h)) memory, but i can't optimize it to work less than 3.5 seconds. Could somebody give me a hint on better solution?

DP works.
Let __int64 F[60][70][3000] is  such array that
F[i][j][k] number of ways to build tower from level i
having at bottom j bricks and k bricks for using.
then F[i][j][k]=F[i+1][j-1][k-j]+F[i+1][j+1][k-j].
But here 4200*3000*8 bytes!?. After thinking we find that
really in his space used 90000 8-places and 590000 4-places.After this we are using structure int **F[60] as store for 4-places and address for 8-places.If data for DP placed compactly all testes processed quickly.


Edited by author 15.12.2008 19:03