AtCoder Beginner Contest 143 [ D - Triangles ] numpy + njit AC Code, https://atcoder.jp/contests/abc143/tasks/abc143_d

abc143_d1.py

'''
[問題]
https://atcoder.jp/contests/abc143/tasks/abc143_d

[解説]
https://atcoder.jp/contests/abc143/editorial/652
 O(N^3)解法を、やってみる

numpy + njitを使わないと、計算速度間に合わない。
これでTLE回避できるのかー。
'''

import sys
import numpy as np
from numba import njit

sys.setrecursionlimit(10 ** 6)  # 再帰上限の引き上げ
input = sys.stdin.readline

INF = 2 ** 63 - 1

N = int(input())
#L = list(map(int, input().split()))
L = np.int32(input().split())
L.sort()

@njit
def f():
    ans = 0

    for i in range(N):
        for j in range(i+1 , N):
            for k in range(j+1, N):
                # ソート済みのLから比較するのでL[i] < L[j] + L[k], L[j] < L[i] + L[k]が成立するの明らか。
                # なので比較は、L[k] < L[i] + L[j]だけで良い
                # 759msでAC
                #ans += (L[k] < L[i] + L[j])

                # こっちでもTLEにならない。1731msくらいでAC
                ans += (L[k] < L[i] + L[j]) and (L[i] < L[k] + L[j]) and (L[j] < L[i] + L[k])

    return ans

print(f())