Thanks.. I was naive enough to use int for some reason, so I fixed the 20, 39 case, but still WA.. =( any cases that are very sensitive to which case to display first?

my algorithm is also using recursion and hashing. I calculate the sums of the paths in the lower part of the Hourglass and store them using STL's map. As a key I use the sum along the path and with it I associate the number of paths with that sum and the first path I found (since I also enumerate the paths in lexicorder).

In the second part of the algorithm I enumerate the paths in the upper part of the Hourglass and try to complement the sum along the path with a sum from the map.

My program outputs correct results for all input I tested but the OJ says TLE. Help me to speed up the program. I think that this is the idea of the solution.

Mine ran in .25, and i basically use the same thing. My guess is that STL is that slow, since I did it in C. I cache on cell and sum, since sum can be at most ~360, so ya.. hope that's enough.. =)

It's not STL per se which causes the TLE, but rather the use of maps.

There is no need whatsoever to use a balanced search tree (i.e. a map) for this problem, you're better of with a vector. maps have a lot worse constant factor than vectors.

I don't know for what reason I decided to use a map. I could index a vector or even an array instead. Now everything is OK (I also found some bugs in my program).

However I didn't know that the map is organized as a balanced search tree. I thought that a hash table is used. So my intention was to use the map exactly as a hash table. So is it true that actually there is no container in STL which I could use as a hash table? Of course SGI provides the hashmap class with their implementation of STL but it is not included in the standard. So the OJ denies it.

I've used the hashmap class in several of my solutions (though the last time was a while ago). Have you really tried this, or do you assume it just because it's not part of the standard? Because in that case, there must have been some change of compiler and/or flags.

But to answer your question: no, in STL by the book, there is currently no container which is guaranteed to work like a hash table (in terms of complexity).