ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1148. Building Towers

How to solve this problem?
Posted by ftc 23 Jan 2007 13:39
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?
Re: How to solve this problem?
Posted by svr 15 Dec 2008 19:00
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