I had ACed with about 1.6 sec running time! I guess the tests for this problem are not strict enought, because I have used very poor O(n^2) algorithm here.