1초로 충분히 풀 수 있습니다. 4초는 2007/2008년 제한이니 1초여도 됩니다.

솔루션과 O(N^2logN)와 동일한 복잡도를 가지는 코드를 짰는데, 공식 데이터에서 1.3s 정도의 시간이 걸렸습니다

1초도 풀 수 있는 시간임에는 동의하지만, O(N^3)을 최적화 하여 푸는 문제임을 고려하면 1.5초나 2초정도가 어떨지 다시 한번 제안해봅니다.