Problem:


Score : 400 points

Problem Statement

Takahashi has N sticks that are distinguishable from each other. The length of the i-th stick is L_i.

He is going to form a triangle using three of these sticks. Let a, b, and c be the lengths of the three sticks used. Here, all of the following conditions must be satisfied:

a < b + c

b < c + a

c < a + b

How many different triangles can be formed? Two triangles are considered different when there is a stick used in only one of them.

Constraints

All values in input are integers.

3 \leq N \leq 2 \times 10^3

1 \leq L_i \leq 10^3

Input

Input is given from Standard Input in the following format:

N
L_1 L_2 ... L_N

Constraints

Print the number of different triangles that can be formed.

Sample Input 1

4
3 4 2 1

Sample Output 1

1

Only one triangle can be formed: the triangle formed by the first, second, and third sticks.

Sample Input 2

3
1 1000 1

Sample Output 2

0

No triangles can be formed.

Sample Input 3

7
218 786 704 233 645 728 389

Sample Output 3

23



Sample input:
4
3 4 2 1


Sample output:
1

Submission status: Accepted

Solution code:
import bisect

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

ans = 0
L = sorted(L)

for i in range(N):
    for j in range(N):
        if i >= j:
            continue
        a = L[i]
        b = L[j]
        c = bisect.bisect_left(L,a+b)
        ans += c - j - 1

print(ans)

Submission status: Accepted

Solution code:
import bisect

N = int(input())
l = list(map(int, input().split()))
l.sort()
count = 0

for i in range(N):
    for j in range(i+1, N):
        count += bisect.bisect_left(l, l[i]+l[j])-j-1
print(count)

Submission status: Accepted

Solution code:
import bisect

n = int(input())
ll = [int(w) for w in input().split()]
ll.sort()

ans = 0
for i in range(n):
    for j in range(i + 1, n):
        ans += bisect.bisect_left(ll, ll[i] + ll[j]) - (j + 1)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from bisect import bisect_left

n, res = int(input()), 0
s = sorted(list(map(int, input().split())))
for i in range(n-1):
    for j in range(i+1, n):
        res += (bisect_left(s, s[i] + s[j])) - (j + 1)
print(res)

Submission status: Accepted

Solution code:
import sys
#import time
from collections import deque, Counter, defaultdict
#from fractions import gcd
import bisect
#import heapq
import math
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))
n = ri()
l = rl()

l.sort()
ans=0
for i in range(n):
    for j in range(i):
        ans+=bisect.bisect_left(l, l[i]+l[j])-(i+1)
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from itertools import combinations 
def main():
    N = int(readline())
    L = [int(i) for i in readline().split()]

    #ソートしておく
    L.sort()

    #最長以外の二辺を先に決める
    #インデックスで二辺を選ぶ。最長の辺はjよりインデックスが大きいものとなることが保証される
    #jより後ろでc<a+bとなる最長の辺cの数を求めれば良い。二分探索で条件を満たす最大の辺を見つけるとよい

    #インデックス用の値を用意
    p = [i for i in range(N)]

    #組みを作る
    idxPairs = [(i, j) for i,j in combinations(p, 2)]

    #jよりインデックスが大きい辺の中から最長の辺を見つける
    ans = 0
    for i, j in idxPairs:
        #j以降を二分探索で調べる
        #最長の辺をL[j]と選ぶと必ず三角形を作ることができる
        l = j
        r = N 
        while r-l>1:
            mid = (r+l)//2
            if L[mid] < L[i]+L[j]:
                l = mid
            else:
                r = mid
        ans += l-j
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
L = sorted(list(map(int, input().split())))

import bisect

ans = 0
for i in range(N):
    for j in range(i+1, N):
        ans += bisect.bisect_left(L, L[i]+L[j]) - (j+1)

print(ans)

Submission status: Accepted

Solution code:
import bisect


N = int(input())
str_l = input()
num = 0
L = []
for v in str_l.split(' '):
    L.append(int(v))

L.sort()
for i in range(N - 1):
    a = L[i]
    for j in range(i, N - 2):
        b = L[j + 1]
        index = bisect.bisect_left(L[j + 2:], a + b)
        num += index
        # for k in range(0, index):
        #     c = (L[j + 2:])[k]
        #     if b + c > a and a + c > b:
        #         num += 1

print(num)

Submission status: Accepted

Solution code:
N = int(input())
L = list(map(int, input().split()))
L.sort(reverse=True)
ans = 0

for i in range(N-2):
    for j in range(i+1, N-1):
        ok = i
        ng = N
        while ng - ok > 1:
            mid = (ok + ng) // 2
            if L[mid] > L[i] - L[j]:
                ok = mid
            else:
                ng = mid
        if ok > j:
            ans += ok - j
            
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
l = sorted(map(int, input().split()))
cnt = 0
m = n-1
g = []
for i in range(n):
  for j in range(i):
    g.append(l[i]+l[j])
g = sorted(g,reverse = True)
for i in g:
  while l[m] >= i:
    m-=1
  cnt += n-m-1
print(n*(n-1)*(n-2)//6-cnt)

Submission status: Accepted

Solution code:
import bisect
n = int(input())
l = list(map(int,input().split()))
l.sort()
ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        r = bisect.bisect_left(l,l[i]+l[j])
        ans += r-(j+1)
print(ans)

Submission status: Accepted

Solution code:
import bisect as bs
N = int(input())
L = list(map(int,input().split()))
L.sort()
ans = 0
for i in range(len(L)-1):
    for j in range(i+1, len(L)):
        ans += bs.bisect_left(L, L[i]+L[j])-j-1
print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

N = int(readline())
L = sorted(list(map(int,readline().split())))

# 2本固定すると、もう一本として選べるのは、2本の和より長いものだけ
# これを二分探索で数える

import bisect
ans = 0
for i in range(N - 1):
  for j in range(i + 1,N):
    ans += bisect.bisect_left(L, L[i] + L[j]) - 1 - j
        
print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

N = int(readline())
L = list(map(int,readline().split()))
L = sorted(L)

# 2本固定すると、もう一本として選べるのは、2本の和より長いものだけ
# これを二分探索で数える

#print(L)
import bisect
ans = 0
for i in range(N - 1):
  for j in range(i + 1,N):
    limit = L[i] + L[j]
    ok = bisect.bisect_left(L, limit)
#    print("i",i,"j",j,"L[i]",L[i],"L[j]",L[j],"limit",limit,"ok",ok,"ok - j",ok - 1 - j)
    ans += ok - 1 - j
        
print(ans)

Submission status: Accepted

Solution code:
import bisect
n = int(input())
L = list(map(int, input().split()))
L.sort()

cnt = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        index = bisect.bisect_left(L[j+1:], L[i] + L[j])
        cnt += index

print(cnt)

Submission status: Accepted

Solution code:
import bisect
n = int(input())
l = sorted(list(map(int,input().split())))

ans = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        ans += bisect.bisect_left(l,l[i] + l[j]) - (j + 1)


print(ans)

Submission status: Accepted

Solution code:
import bisect

n = int(input())
l = list(map(int, input().split()))
l.sort()

ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        idx = bisect.bisect_left(l, l[i]+l[j])
        ans += idx-j-1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
l.sort(reverse=True)
c=0
for i in range(n-2):
  for j in range(i+1,n-1):
    u=l[i]-l[j]
    if l[j+1]<=u:
      break
    ok=j+1
    ng=n
    while ng-ok>1:
      center=(ok+ng)//2
      if l[center]>u:
        ok=center
      else:
        ng=center
    c+=ng-j-1
print(c)

Submission status: Accepted

Solution code:
#(0)入力環境
import bisect#listをsortしたまま要素を挿入できる
n = int(input())
l = sorted(list(map(int,input().split())))

#(1)考察
#aとbの二重ループのなかで最後の一つは二分探索で高速に
ans = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        ans += bisect.bisect_left(l,l[i] + l[j]) - (j + 1)
        

print(ans)

Submission status: Accepted

Solution code:
import bisect
n=int(input())
L=sorted(list(map(int,input().split())))
ans=0
for i in range(n-1):
    for j in range(i+1,n):
        ans+=bisect.bisect_left(L,L[i]+L[j])-(j+1)
print(ans)

Submission status: Accepted

Solution code:
import bisect
n=int(input())
l=sorted(list(map(int,input().split())))
ans=0
for i in range(n-1):
  for j in range(i+1,n):
    ans+=bisect.bisect_left(l,l[i]+l[j])-(j+1)
print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    L = sorted(list(map(int, input().split())))
    ans = 0
    for ia in range(N-2):
        a = L[ia]
        ic = ia + 2
        for ib in range(ia+1, N-1):
            b = L[ib]
            while ic < N and L[ic] < a+b:
                ic += 1
            ans += ic - (ib + 1)
    print(ans)
main()

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

read = sys.stdin.buffer.read


def main():
    N, *L = map(int, read().split())

    L.sort()
    max_L = L[-1]

    C = [0] * (max_L + 1)
    for l in L:
        C[l] += 1
    C = list(accumulate(C))

    ans = 0
    for i in range(N):
        for j in range(i + 1, N):
            if L[i] + L[j] > max_L:
                ans += N - j - 1
            else:
                ans += C[L[i] + L[j] - 1] - j - 1

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

read = sys.stdin.buffer.read


def main():
    N, *L = map(int, read().split())

    L.sort()
    max_L = L[-1]

    C = [0] * (max_L + 1)
    for l in L:
        C[l] += 1
    C = list(accumulate(C))

    ans = 0
    for i, a in enumerate(L):
        for j, b in enumerate(L[i + 1 :], i + 1):
            if a + b > max_L:
                ans += N - j - 1
            else:
                ans += C[a + b - 1] - j - 1

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *L = map(int, read().split())

    L.sort()

    max_L = max(L)

    C = [0] * (max_L + 1)
    for l in L:
        C[l] += 1
    C = list(accumulate(C))

    ans = 0
    for i, a in enumerate(L):
        for j, b in enumerate(L[i + 1 :], i + 1):
            if a + b > max_L:
                ans += N - j - 1
            else:
                ans += C[a + b - 1] - j - 1

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left, bisect_right

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *L = map(int, read().split())

    L.sort()

    ans = 0
    for i, a in enumerate(L):
        for j, b in enumerate(L[i + 1 :], i + 1):
            k = bisect_left(L, a + b, lo=j + 1)
            ans += k - j - 1

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
n = int(input())
l = sorted(list(map(int, input().split())))

ans = 0
for i in range(n-1):
  for j in range(i+1, n):
    ans += bisect.bisect_left(l, l[i]+l[j]) - (j+1)
print(ans)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left, bisect_right

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *L = map(int, read().split())

    L.sort()

    ans = 0
    for i in range(N):
        a = L[i]
        for j in range(i + 1, N):
            b = L[j]
            left = bisect_left(L, b, lo=j + 1)
            right = bisect_left(L, a + b, lo=j + 1)
            ans += right - left

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left, bisect_right

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *L = map(int, read().split())

    L.sort()

    ans = 0
    for i in range(N):
        a = L[i]
        for j in range(i + 1, N):
            b = L[j]
            left = bisect_left(L, b, lo=j + 1)
            right = bisect_left(L, a + b)
            ans += right - left

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
n = int(input())
l = list(sorted(map(int, input().split())))


'''
a,bの値を指定し、その合計値を下回る値の最大値のインデックス番号を取得
インデックス番号から指定していたb（大きい方の値）を引く
'''
ans = 0
for a in range(n):
  for b in range(a+1, n):
    ans += bisect.bisect_left(l, l[a]+l[b]) - (b+1)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit
 

@njit
def f(a):
    n = len(a)
    cnt = 0
    
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if a[k] < a[i] + a[j]:
                    cnt += 1
    return cnt


n = int(input())
a = np.array(input().split(), dtype=np.int32)
a.sort()
print(f(a))

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit
 

@njit
def f(A):
    n = len(a)
    cnt = 0
    
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                cnt += (A[k] < A[i] + A[j])
    return cnt


n = int(input())
a = np.array(input().split(), dtype=np.int32)
a.sort()
print(f(a))

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit
 

@njit
def f(A):
    N = len(A)
    cnt = 0
    
    for i in range(N):
        for j in range(i + 1, N):
            for k in range(j + 1, N):
                cnt += (A[k] < A[i] + A[j])
    return cnt


N = int(input())
A = np.int32(input().split())
A.sort()
print(f(A))

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit
 
@njit
def f(A):
  N = len(A)
  cnt = 0
  for i in range(N):
    for j in range(i + 1, N):
      for k in range(j + 1, N):
        cnt += (A[k] < A[i] + A[j])
  return cnt
 
N = int(input())
A = np.int32(input().split())
A.sort()
print(f(A))

Submission status: Accepted

Solution code:
import itertools
 
n = int(input())
A = list(map(int,input().split()))
A.sort()
 
def binary_search(l,r,v):
    while r >= l:
        h = (l+r) // 2
        if A[h] < v:
            l = h+1
        else:
            r = h-1
    return r
 
ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        a = binary_search(j,n-1,A[i]+A[j])
        ans += a-j
 
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

def main():
    N = int(input())
    L = sorted(list(map(int, input().split())))

    ans = 0
    for ia in range(N):
        for ib in range(ia+1, N-1):
            a = L[ia]
            b = L[ib]
            ic_end = bisect_left(L, a+b, lo=ib+1)
            ans += ic_end - (ib+1)

    print(ans)
main()

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

def main():
    N = int(input())
    L = sorted(list(map(int, input().split())))

    ans = 0
    for ia in range(N):
        for ib in range(ia+1, N-1):
            a = L[ia]
            b = L[ib]

            c_min = max(a-b, b-a)
            c_max = a + b
            ic_begin = bisect_right(L, c_min, lo=ib+1)
            ic_end   = bisect_left( L, c_max, lo=ib+1)

            ans += ic_end - ic_begin

    print(ans)
main()

Submission status: Accepted

Solution code:
N = int(input())
L = list(map(int, input().split()))

L.sort()

# print(L)
import bisect
ans = 0
for i in range(N-2):
    l1 = L[i]
    for j in range(i+1, N-1):
        l2 = L[j]
        l3_max = (l1 + l2)

        k = bisect.bisect_left(L, l3_max, lo=j+1)
        ans += max(0, k - j - 1)
print(ans)

Submission status: Accepted

Solution code:
import bisect
 
N = int(input())
Ls = list(map(int, input().split(" ")))
Ls.sort()
 
ans = 0
 
for i in range(0,N-2):
  for j in range(i+1,N-1):
    k = bisect.bisect_left(Ls,Ls[i]+Ls[j])
    ans += k - (j + 1)
       
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
L = list(map(int,input().split()))
L = sorted(L)
import bisect
ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        a = bisect.bisect_left(L,L[i]+L[j])
        ans += a-j-1
print(ans)

Submission status: Accepted

Solution code:
import bisect

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

ans = 0
for i in range(len(L)-2):
    for j in range(i+1, len(L)-1):
        ans += bisect.bisect_left(L, L[i]+L[j])-j-1    
print(ans)

Submission status: Accepted

Solution code:
import bisect

n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
for i in range(n - 2):
    for j in range(i + 1, n - 1):
        ans += bisect.bisect_left(l, l[i] + l[j]) - j - 1
print(ans)

Submission status: Accepted

Solution code:
import sys, bisect

N = int(input())
L = list(map(int, sys.stdin.readline().rsplit()))
L.sort()

res = 0
for i in reversed(range(1, N)):
    for j in reversed(range(i)):
        r = bisect.bisect_right(L, abs(L[i] - L[j]))
        
        if r < j:
            res += j - r
        
print(res)

Submission status: Accepted

Solution code:
import sys, bisect

N = int(input())
L = list(map(int, sys.stdin.readline().rsplit()))
L.sort()

res = 0
for i in reversed(range(1, N)):
    for j in reversed(range(i)):
        l = bisect.bisect_left(L, L[i] + L[j])
        # r = bisect.bisect_right(L, abs(L[i] - L[j]))
        
        res += l - 1 - i
        
print(res)

Submission status: Accepted

Solution code:
import bisect
n = int(input())
l = list(sorted(map(int,input().split())))
count = 0
for i in range(n):
    for j in range(i+1,n):
        count += bisect.bisect_left(l, l[i] + l[j]) - (j + 1)
print(count)

Submission status: Accepted

Solution code:
from bisect import bisect_left
n = int(input())
l = list(map(int,input().split()))
l = sorted(l)
cnt = 0
for i in range(n):
    for j in range(i+1,n):
        #print(l[i],l[j])
        cnt += bisect_left(l, l[i] + l[j]) - (j + 1)
print(cnt)

Submission status: Accepted

Solution code:
from bisect import bisect
from bisect import bisect_right
from bisect import bisect_left
 
N = int(input())
L = list(map(int, input().split()))
L.sort()
#print(L)
 
cnt = 0
for i in range(N):
  for j in range(i+1, N):
    s = L[i] + L[j]
    x = bisect_left(L, s)
    #print((L[i], L[j]), s, x)
    cnt += max(x - j - 1, 0)
print(cnt)

Submission status: Accepted

Solution code:
import bisect

n = int(input())
ll = list(map(int, input().split()))
ll.sort()

ans = 0
for i in range(n-2):
    e1 = ll[i]
    for j in range(i+1, n-1):
        e2 = ll[j]
        cnt = bisect.bisect_left(ll, e1+e2)
        cnt -= (j+1)
        ans += max(cnt,0)

print(ans)

Submission status: Accepted

Solution code:
import bisect

n = int(input())
ll = list(map(int, input().split()))
ll.sort()

ans = 0
for i in range(n-2):
    e1 = ll[i]
    for j in range(i+1, n-1):
        e2 = ll[j]
        comb = bisect.bisect_left(ll[j+1:], e1+e2)
        # comb -= (j+1)
        ans += max(comb,0)

print(ans)

Submission status: Accepted

Solution code:
import bisect

n = int(input())
ll = list(map(int, input().split()))
ll.sort()

ans = 0
for i in range(n-2):
    e1 = ll[i]
    for j in range(i+1, n-1):
        e2 = ll[j]
        comb = bisect.bisect_left(ll, e1+e2)
        comb -= (j+1)
        ans += max(comb,0)

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

N = int(input())
L = list(map(int, input().split()))
L.sort(reverse=True)
#print(L)
ans = 0

"""
これだとTLEしてしまう
for i in range(N-2):
    for j in range(i+1, N-1):
        left = j
        right = N
        target = L[i]-L[j]
        while right-left > 1:
            mid = (right + left)//2
            #print(mid)

            if L[mid] > target:
                left = mid
            else:
                right = mid

        ans += left-j
        """

L.sort()
for i in range(N):
    for j in range(i+1, N):
        target = L[i]+L[j]
        left = bisect_left(L, target) #二分探索の関数
        ans += max(0, left-j-1)


print(ans)

Submission status: Accepted

Solution code:
import bisect

N = int(input())
numbers = [int(i) for i in input().split()]
numbers = sorted(numbers)
counter = 0

for a in range(N):
    for b in range(a+1, N):
        c = bisect.bisect_left(numbers, numbers[a] + numbers[b])
        if c > b:
            counter += c - b -1
        
print(counter)

Submission status: Accepted

Solution code:
import bisect
n = int(input())
l = list(map(int, input().split()))
sort_l = sorted(l)
count = 0

for a in range(n):
    for b in range(a+1, n):
        c = bisect.bisect_left(sort_l, sort_l[a] + sort_l[b])
        if c > b:
            count += c - b -1
        else:
            pass     
        

print(count)

Submission status: Accepted

Solution code:
import bisect
n=int(input())
l=sorted(list(map(int,input().split())))
g=0
for ai in range(n-2):
    for bi in range(ai+1,n-1):
        g+=max(0,bisect.bisect_left(l,l[bi]+l[ai])-1-bi)
print(g)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import collections
import bisect

def main():
    n = int(input())
    l = input_list()
    l.sort()
    ans = 0
    for i in range(n-2):
        for j in range(i+1, n-1):
            ind = bisect.bisect_left(l, l[i]+l[j])
            num = ind - 1 - j
            ans += num
    print(ans)


def input_list():
    return list(map(int, input().split()))


def input_list_str():
    return list(map(str, input().split()))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left
N=int(input())
A=sorted(list(map(int,input().split())))
cnt=0
for i in range(N-1):
    for j in range(i+1,N):
        a=bisect_left(A,A[i]+A[j])
        if j<a:
            cnt+=a-j-1
print(cnt)

Submission status: Accepted

Solution code:
import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
from itertools import combinations
import bisect
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
a=ii()
l=list(mi())
l=sorted(l)
ans=0
for i in range(a-2):
  for j in range(i+1,a-1):
    s=bisect.bisect_left(l,l[i]+l[j])
    ans+=s-j-1
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
N=int(input())
triangle=[]
count=0
L=list(map(int,input().split()))
L.sort()
#print(L)
for a in range(N):
    for b in range(a+1,N):
        c=L[a]+L[b]
        zahyo=bisect_left(L,c)
        count+=max(0,zahyo-b-1)
print(count)

Submission status: Accepted

Solution code:
from bisect import bisect_left
N=int(input())
triangle=[]
count=0
L=list(map(int,input().split()))
L.sort()
#print(L)
for a in range(N):
    for b in range(a+1,N):
        c=L[a]+L[b]
        zahyo=bisect_left(L,c)
        count+=max(0,zahyo-b-1)
print(count)

Submission status: Accepted

Solution code:
import bisect

n = int(input())

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

A = sorted(L)

ans = 0

for i in range(n):
    for j in range(i+1,n):
        total = L[i] + L[j]
        ans += bisect.bisect_left(A,total) - (j+1)

print(ans)

Submission status: Accepted

Solution code:
import itertools
import bisect

n = int(input())

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

A = sorted(L)

ans = 0

for i in range(n):
    for j in range(i+1,n):
        total = L[i] + L[j]
        ans += bisect.bisect_left(A,total) - (j+1)

print(ans)

Submission status: Accepted

Solution code:
import itertools
import bisect

n = int(input())

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

A = sorted(L)

ans = 0

for i in range(n):
    for j in range(i+1,n):
        total = L[i] + L[j]
        ans += bisect.bisect_left(A,total) - (j+1)

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
n = int(input())
L = sorted(list(map(int, input().split())))
#print(L)
ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        ans += bisect_left(L,L[i]+L[j])-(j+1)
        #print(i,j,bisect_left(L,L[i]+L[j]),(j+1))
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

n = int(input())
a = list(map(int,input().split()))
a.sort()

ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        ind = bisect_left(a,a[i]+a[j])
        ans += ind-j-1

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
n = int(input())
L = list(map(int, input().split()))
L.sort()

cnt = 0
for a in range(n-2):
    for b in range(a+1, n-1):
        cnt += bisect_left(L,L[a]+L[b])-(b+1)
print(cnt)

Submission status: Accepted

Solution code:
import bisect
 
n = int(input())
a = list(map(int,input().split()))
a.sort()

ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        index = bisect.bisect_left(a,a[i]+a[j])
        ans += index-j-1
        
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
n=int(input())
a=list(map(int,input().split()))
a.sort()

ans=0
# print(a)
for i in range(1,n-1):
    for j in range(0,i):
        k=bisect_left(a,a[i]+a[j])-i-1
        # print(f"i{i} j{j} bisect{bisect_left(a,a[i]+a[j])}")
        ans=ans+k
print(ans)

Submission status: Accepted

Solution code:
import bisect
n = int(input())
l_li = list(map(int,input().split()))
l_li.sort()
ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        ind = bisect.bisect_left(l_li,l_li[i]+l_li[j])
        ans += ind-1 - j
print(ans)

Submission status: Accepted

Solution code:
import bisect
n = int(input())
l_li = list(map(int,input().split()))
l_li.sort()
ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        ind = bisect.bisect_left(l_li,l_li[i]+l_li[j])
        num = ind-1 - j
        ans += num
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
n=int(input())
a=list(map(int,input().split()))
a.sort()

ans=0
for i in range(1,n-1):
  for j in range(0,i):
    k=bisect_left(a,a[i]+a[j])-i-1
    ans=ans+k
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    *L, = map(int, input().split())
    L.sort()
    ans = 0
    for i in range(2, N):
        for j in range(i):
            k = bisect_right(L, L[i] - L[j], j + 1, i)
            ans += i - k
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left

n = int(input())
l = sorted(list(map(int, input().split())))

#aを1番短い辺、bを2番めに短い辺とする
cnt = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        c_i = bisect_left(l, l[i] + l[j])
        cnt += c_i - (j+1)

print(cnt)

Submission status: Accepted

Solution code:
import bisect
n = int(input())
l_li = list(map(int,input().split()))
l_li.sort()
ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        ind = bisect.bisect_left(l_li,l_li[i]+l_li[j])
        num = ind-1 - j
        if num > 0:
            ans += num
print(ans)

Submission status: Accepted

Solution code:
import bisect

N = int(input())
L = list(map(int,input().split()))
L = sorted(L)
ans = 0

for i in range(N-2) :
    for j in range(i+1,N-1) :
        a = L[i] + L[j]
        X =bisect.bisect_left(L,a)
        ans += X- j - 1
        
    
print(ans)

Submission status: Accepted

Solution code:
import bisect

N = int(input())
L = [int(n) for n in input().split()]
L = sorted(L)

total = 0

for i in range(N - 2):
    a = L[i]
    for j in range(i + 1, N - 1):
        b = L[j]
        right_endpoint = bisect.bisect_left(L, a+b, j)
        total += right_endpoint - j - 1

print(total)

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import os
import bisect

# 検索用タグ、尺取り、3つの内2つを固定
# https://drken1215.hatenablog.com/entry/2019/10/20/032700

# 実装を行う関数
def resolve():
    n = int(input())
    ls = list(map(int, input().split()))

    ls.sort()

    ans = 0
    # 尺取り
    for i in range(n - 2):
        a = ls[i]
        for j in range(i + 1, n - 1, 1):
            b = ls[j]
            # 以下がサンプル通りだが、TLE。
            # for k in range(j + 1, n, 1):
            #     c = ls[k]
            #     if not c < a + b:
            #         break
            #     ans += 1
            cnt = bisect.bisect_left(ls, a + b, j)
            ans += cnt - j - 1

    print(ans)


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """4
3 4 2 1"""
        output = """1"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """3
1 1000 1"""
        output = """0"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """7
218 786 704 233 645 728 389"""
        output = """23"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Accepted

Solution code:
import bisect
n = int(input())
l = list(map(int,input().split()))
l.sort()
count = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        maxc = l[i]+l[j] #短い2辺の和
        index = bisect.bisect_left(l, maxc)
        if index > j:
            count += index-j-1
print(count)

Submission status: Accepted

Solution code:
import itertools
import bisect

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

L = sorted(L)

count = 0

for i in range(N - 2):
    for j in range(i + 1, N - 1):
        x, y = L[i], L[j]
        limit = x + y
        index = bisect.bisect_left(L, limit)
        count += max(0, index - j - 1)

print(count)

Submission status: Accepted

Solution code:
import itertools, bisect

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):
        cindex = bisect.bisect_left(L, int(L[i]) + int(L[j]))
        ans += cindex-1 - j

print(ans)

Submission status: Accepted

Solution code:
import bisect
n = int(input())
edges = sorted(list(map(int, input().split(' '))))
ans = 0
for i in range(n-1, -1, -1):
  for j in range(i-1, -1, -1):
    limit = edges[i] - edges[j]
    if limit < edges[j]:
      index = bisect.bisect_right(edges, limit)
      ans += max(0, j - index)  # maxいらんかも
print(ans)