問題

解法その1　numpy + njitを使ったO(N³)解法　

なんと、何も考えずに問題通り、総当たりコードを書くとACしてしまうという解法。
マジですか。

AtCoderのPythonではnumpyが使用できるが、njitを使って関数の実行速度を高速化。
実行すると、1731msくらいでACする。

問題の制約が、3 < N < 2 * 10³。
とすると、O(N³)は、(2 * 10³)³なので、8 * 10⁹。
10⁸をオーバーするので、普通はTLEだろうと見込んでスルーする実装だが、njitを使うことで実は間に合ってしまう。

なるほどねー。わからないから、とりあえずnjitでも使ってみるか。
という選択肢もアリってことかな？

とりあえず作問した人は想定してなかった解答だろうな。

問題の制約が、3 < N < 2 * 10³。
全探索は10⁹オーバーなので、数学的な最適化を狙う方法。
atcoderの通常パターンなら、こう考えるべきだがw

a < b < c と考える。
a, bに総当たりならば(2 * 10³)² = 4 * 10⁶。
cの値は計算で求める。
c < a + b
であるあから、a + b以下の要素がLの中に何個あるかを二分探索で求める。
cはbより大きいから、b+1以上の要素が下限。

Lの中からa+b以下、b+1以上の要素数を引き算で出せば終了。
計算量はO( N² logN)