it's based just on randomization+DP and the runtime goes from 0.046 to 0.23 sec depending on the seed used.
I don't know if it can be beat easily.
It's a very simple program, by the way.

Edited by author 01.09.2006 17:52

After some improvements, the runtime does not vary much and I got a 0.015 sec AC.
Hope admins add some more tests or increase the size of the test cases so I can see if my solution is good for something.