Brute force with tc O(n^3) works?!That too in a contest?

Is there really no other efficient approach other than brute force for this problem?
Because brute force seems to be working just fine for that kind of input.

The tests were too weak. As the problem specified number of testcases can be 10^5 and N can be 1024. Therefore in worst case the O(n^3) algorithm will surely take TLE. I can provide many test cases where the accepted O(n^3) solutions will fail. It is unacceptable. @admin please look into it.