So recently I was in an SRM, and was solving this problem, I will attach an image as it's not posted yet outside the applet. ( If you would like to check in the applet, it's Div1 694 250)
http://imgur.com/sLxbFSV (^There is an option to zoom in).
Each element is between 0 and 255, and size of the array is at most 50.
Solution is Dynamic Programming in O(255*255*51*8).
After the round I got TLE, I thought it was maybe Java TLEing on a max case, but instead it looks like I TLE'd on a case where n = 5 ( lol ) yet my code passes for cases where N is nearly 50. C++ as copy paste from java passes all tests in around 300ms.
Now how can my code be passing cases where N is nearly 50 yet TLE on this one ? It just doesn't make sense...I did run it on my own machine, and it was fine.
A red guy in my room as well couldn't find anything wrong with, and just said it's weird. That's why I'm here CF :).
If this is a max case, I'd try to convince myself that the recursion overhead is too much, but N is just 5..
Incase you would like to have a look at the code, here you go :
It also takes 850ms on CF Servers...
