AtCoder Beginner Contest 143 [ D - Triangles ] 想定解 https://atcoder.jp/contests/abc143/tasks/abc143_d

abc143_d2.py

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

[解説]
https://youtu.be/3U_N7zelnMM?t=2984

https://img.atcoder.jp/abc143/editorial.pdf

a, bを総当たり(2 * 10^3)^2 で 4 * 10^6
c に関しては二分探索で本数を求める
c < a + b
なので、L内にa + bがどこに入るか？をしらべbの添字から引くとcが出る

計算量 O(N^2 logN)
'''

import sys
import bisect

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

INF = 2 ** 63 - 1

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

ans = 0

for i in range(N):
    for j in range(i+1, N):
        a = L[i]
        b = L[j]

        # cの本数を数える。c = [l, r)
        # r は a + bがL内のどの位置に入るか？
        r = bisect.bisect_left(L, a + b)
        c_cnt = r - (j + 1)

        ans += c_cnt

print(ans)