Sorry if I sounded rude, Adrian, I meant it's fishy that 95% of people didn't find out that both LIS and simple greedy are fundamentally incorrect.
Well, it seems like I have got AC again, by modifying the greedy algorithm. It now uses construction approach:
1. start with an empty stack
2. in each step try to add one turtle ANYWHERE in or on or below the stack, in such the manner that total remaining strength of the stack is maximal
3. repeat step 2 while possible
This algorithm has solved all samples from these posts, and also got AC. It solves, for instance, trivial case with two turtles that cannot be solved with simple greedy algorithm:
Correct answer is obviously 2, but simple greedy that puts new turtle always on top of the current stack would give result 1 by taking 5 15 turtle (that has max(remaining strength), and then gets stuck.
Real reason why simple greedy or one-dimensional LIS do not work here is because they both rely on some kind of sorting, with fixed and predefined sorting criterion. When I say fixed criterion (say, relation R), I mean that sorting is a recurrent operation where array of N elements is sorted if its first N-1 elements are sorted and Nth element is in relation R with all elements before it. One of the tricks that make greedy and LIS algorithms nice (and often hard to prove) is that relation R doesn't have to be transitive as it normally is in plain sorting problems.
I am not sure about the proof of the algorithm above. For example, I haven't proved exactly how to resolve multiple solutions in one step although I did it somehow. As for now, I am AC and out, and I hope there will be no further counter examples that would make my solution WA again
. I just hope that I've learned something out of this problem.