Accepted
0.062    1 486 КБ

I solve this problem with O(log K*(K+(W*H)^2)).

P.S. Sorry for my bad English.

My algo's complexity is the same (haven't applied yet). Maybe, author have less efficient algo. Maybe, you realization is pretty fast...

Well, the solution and the tests for this problem were written when I had just finished the first course. I had been quite a "weak" programmer that time. Actually, I'd implemented the first solution that came in my head and designed TLs and tests for it. Certainly, this problem had been stored on HDD without any change for one and a half year, and then it was given to the PTZ camp. Yes, we designed a lot of more efficient solutions, but it was laziness that prevented me from implementing them and creating new tests.

Nevertheless, probably it would be better for the tests to be unchanged. As I can see, this problem remains a great challenge for Timus coders, and the main difficulty is not to fit the speed limits.

Still, I think TL is too large. Now I wrote it and also got AC in 0.062 sec. I think that 1 sec. for this problem is more than enough...

I agree because even obvious O(W*H*K) solution, written quite optimal, works less then 0.5 sec.

Hm... This, IMHO, already means that testset is weak, and admins should try to improve it

I think it's strange to discuss large TL and weak tests for problem that was solved by 12 people on Timus (and one of them is the author of this problem).