Hi.
Is O(N^2) solution good for this problem? I got TL on 8th test. Should I reduce constant in O() or should I find N*logN solution? It's strange that 25M operations take over 2 seconds.

Ofc no; the max N is 10^5, so N^2 would be 10^10; thats about 50 seconds to do such number of operations on a normal PC

N^2 is almost never acceptable if N exceeds ~4000-5000.
I attempted to think a bit at this task... as far as i understood, for flowers with a certain dryness X, let us assume that the leftmost flower with such dryness is X1, the rightmost is X2, Kirill's position is Y. Cases like Y...X1...X2 and X1...X2...Y are easy, Kirill needs to go to the rightmost and to the leftmost flower respectively, but in case of X1...Y...X2 it gets a bit harder. At first, i assumed that we should just go first to the side that we're closer to, but then, i found out a counter test for that:
19
2 9 9 9 9 9 9 9 1 9 9 9 9 9 9 2 3 4 5
Initial path to the right 2, through 6 nines, is shorter than to the left 2, through 7 nines, but eventually this turns out to be a bad decision, since we have to go all the way to the right again. So probably, we should somehow take a group of flowers with next closest dryness into consideration. I'll try to think of it some more when i'm not lazy...

Hello! I solved this problem O(N*logN). Idea=Sort+Dp[i,x],where x=the most Right and the most Left

Yes. I thought it is 10^4. I was neglectful.

.

Edited by author 05.11.2015 18:28

...

Edited by author 07.11.2015 13:32

19
2 9 9 9 9 9 9 9 1 9 9 9 9 9 9 2 3 4 5
70, btw for java AC long for path[] is enough (BigInteger works slower few milliseconds)