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()))
l.sort()
ans = 0
for i in range(1,N-1):
  for j in range(i+1,N):
    m=bisect.bisect_right(l,l[j]-l[i])
    if i>m:
      ans+=i-m
print(ans)

Submission status: Accepted

Solution code:
import sys
import bisect
N = int(input())
L = [i for i in map(int, input().split())]
ans = 0

L.sort()
#print(L)
if N == 3:
    if L[0] + L[1] > L[2]:
        print("1")
        sys.exit()

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

Submission status: Accepted

Solution code:
import sys
import bisect
N = int(input())
L = [i for i in map(int, input().split())]
ans = 0

L.sort()
#print(L)
if N == 3:
    if L[0] + L[1] > L[2]:
        print("1")
        sys.exit()

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect
N = int(input())
Ls = list(map(int, input().split()))
 
Ls = sorted(Ls)
cnt = 0
for i in range(N):
    l1 = Ls[i]
    for j in range(i+1, N):
        l2 = Ls[j]
        ind = bisect.bisect_left(Ls, l1 + l2)
        cnt += ind - j - 1
print(cnt)

Submission status: Accepted

Solution code:
import sys
from itertools import combinations
from bisect import bisect_left

def main():
    input = sys.stdin.readline
    N = int(input())
    L = list(map(int, input().split()))

    L = sorted(L)
    ans = 0
    for a, b in combinations(range(N), 2):
        a, b = min(a, b), max(a, b)

        c_max = L[a] + L[b]

        left = b + 1
        right = bisect_left(L, c_max)

        ans += right - left

    return ans

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
from bisect import*
_,l=open(0)
l=sorted(map(int,l.split()))
print(sum(j-bisect(l,a-l[j],0,j)for i,a in enumerate(l)for j in range(i)))

Submission status: Accepted

Solution code:
import itertools
import bisect

def D():
    n = input()
    l = map(int,input().split(" "))
    temp = itertools.combinations(l,3)
    count = 0
    #print(temp)
    #res = [i for i in temp if i[0] < i[1]+i[2] and i[1] < i[0]+i[2] and i[2] < i[0]+i[1]]
    for i in temp:
        i = sorted(list(i),reverse=True)
        if i[0] < i[1]+i[2]:
            count += 1
    print(count)

def D_sort():
    N = int(input())
    L = sorted([int(_) for _ in input().split()])
    #L[a] + L[b] > L[c]
    ans = 0
    for a in range(N - 2):
        for b in range(a + 1, N - 1):
            ans += bisect.bisect(L, L[a] + L[b] - 1) - b - 1
            #右挿入二分探索で得たインデックス-2つ目に長い辺のインデックス=その2辺で作れる三角形の個数
            #(この間に入っている辺を使う分には三角形成立条件が必ず満たされている)
    print(ans)
if __name__ == '__main__':
    D_sort()

Submission status: Accepted

Solution code:
import bisect
import math

def main():
    n = int(input())
    l_s = list(sorted(map(int, input().split(' '))))

    ans = 0

    for c in range(2, n):
        for b in range(1, c):
            idx = bisect.bisect_right(l_s, l_s[c] - l_s[b])
            idx = min(b, idx)
            ans += b - idx
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------
from bisect import bisect_left  as bl
from bisect import bisect_right as br
from bisect import insort_left  as il    # insort_leftはO(N)
from bisect import insort_right as ir
#-------------------------------------------------------------------
n = int(input())
L = list( map(int, input().split()) )	# 1 2 3 4 5 ...

L.sort()

ans=0

for i in range(n-2):
	a=L[i]
	
	for j in range(i+1, n-1):
		b=L[j]
		
		k = bl(L,a+b)
		
		ans+=k-j-1

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right

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

ans = 0
for i in range(1, N-1):
    for j in range(i+1, N):
        ans += max(0, i - bisect_right(L, L[j] - L[i]))
print(ans)

Submission status: Accepted

Solution code:
# 本番では解けず。
from sys import stdin
import bisect

N = int(stdin.readline())
L = [int(x) for x in stdin.readline().rstrip().split()]

# (1)Lを昇順にソートする
L.sort()

s = 0

for i in range(N-2):
    for j in range(i+1, N-1):

        # (2)Lから2つの辺を固定で選ぶ（L[i]をa L[j]をbとする）
        # この場合、a < b + c, b < a + c はソート済みのため自明。
        # c < a + b が成り立つ棒の個数を調べる
        tmp = L[i] + L[j]

        # (3)Lの中から(2)の和(a+b)、を左に挿入できる場所二分探索で探す
        # つまりL[index - 1] < L[i] + L[j] < L[index] になるindexを探す。

        index = bisect.bisect_left(L, tmp)

        # (4) 固定で選んだ大きい方の辺から(3)で見つけた棒の間にある棒の個数を足す
        # b より右にあり、これより左にあるもの　→　開区間　(L[j], L[index])に含まれる棒は c < a + b を満たすので。
        s += (index - (j+1))

print(s)

Submission status: Accepted

Solution code:
import sys
import math
import copy

def main():
    n = int(input())
    l = [int(t) for t in input().split()]

    # まずはLを昇順にソートする
    l.sort()
    
    count = 0
    # 1番短い棒(i)と2番目に短い棒(j)を決める
    for i in range(0, n):
        for j in range(i+1, n):
            lb, ub = j, n
            while ub - lb > 1:
                half = (lb + ub) // 2
                if l[half] < l[i] + l[j]:
                    lb = half
                else:
                    ub = half
            count += ub - (j + 1)

    print(count)

    return 0

if __name__ == '__main__':
    sys.exit(main())

Submission status: Accepted

Solution code:
from bisect import bisect_left
from bisect import bisect_right


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

"""
短いほうから２本固定して条件に合うものをさがす（長いほうから２本固定でもOK）
最長と最短を固定するとややこしくなるから、こういう場合は最長/最短どちらかから固定するほうがいいか
"""


ans = 0
for i in range(N-2):
    #a = L[i]

    for j in range(i+1, N-1):
        #b = L[j]
        # そもそもcがaやbより大きいので、下の解法のようにilを求める必要などなく、il=で考えれば良かったんや！
        # 下のbisectでlo=~を指定すると遅くなりTLE。内部でL[j:]のlistを新たに生成して、そこにbisectしてるっぽく、list生成するので遅い
        #k = bisect_left(L, a+L[j])
        k = bisect_left(L, L[i]+L[j])
        ans += k - j - 1



"""
ans = 0
for i in range(N):
    for j in range(i+1, N):
        l = L[j] - L[i]
        r = L[j] + L[i]
        #  a < b < c（場合によっては等号を含む）で考えたときの、b - a < cを満たすもの 
        il = bisect_right(L, l, lo=j)
        #  a < b < c（場合によっては等号を含む）で考えたときの、c < a + bを満たすもの
        ir = bisect_left(L, r, lo=j)
        # b - a < cを満たすものがない場合、飛ばす
        if il == N-1:
            break
        
        ans += ir - il - 1
"""

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
ll = list(map(int, input().split()))
ll.sort(reverse=True)

ans = 0

for i in range(n-2):
    j = i + 1
    k = n - 1
    while k > j:
        if ll[i] < ll[j] + ll[k]:
            ans += k - j
            j += 1
        else:
            k -= 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
Lines = list(map(int, input().split(" ")))
Lines.sort()
answer = 0
 
import bisect
 
for lineI in range(N):
    for lineJ in range(lineI+1,N):
    	answer += bisect.bisect_left(Lines,Lines[lineI]+Lines[lineJ])-lineJ-1
print(answer)

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

L.sort()
result = 0
for i in range(N - 2):
    a = L[i]
    for j in range(i + 1, N - 1):
        result += bisect_left(L, a + L[j]) - j - 1
print(result)

Submission status: Accepted

Solution code:
from bisect import bisect_left
from bisect import bisect_right


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

"""
短いほうから２本固定して条件に合うものをさがす（長いほうから２本固定でもOK）
最長と最短を固定するとややこしくなるから、こういう場合は最長/最短どちらかから固定するほうがいいか
"""


ans = 0
for i in range(N-2):
    #a = L[i]

    for j in range(i+1, N-1):
        #b = L[j]
        # そもそもcがaやbより大きいので、下の解法のようにilを求める必要などなく、il=で考えれば良かったんや！
        #k = bisect_left(L, a+L[j])
        k = bisect_left(L, L[i]+L[j])
        ans += k - j - 1



"""
ans = 0
for i in range(N):
    for j in range(i+1, N):
        l = L[j] - L[i]
        r = L[j] + L[i]
        #  a < b < c（場合によっては等号を含む）で考えたときの、b - a < cを満たすもの 
        il = bisect_right(L, l, lo=j)
        #  a < b < c（場合によっては等号を含む）で考えたときの、c < a + bを満たすもの
        ir = bisect_left(L, r, lo=j)
        # b - a < cを満たすものがない場合、飛ばす
        if il == N-1:
            break
        
        ans += ir - il - 1
"""

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
from bisect import bisect_left
for i in range(n):
    a = l[i]
    for j in range(i+1, n):
        b = l[j]
        x = a + b
        c = bisect_left(l, x)
        ans += c - 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()
result = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        result += bisect_left(L, L[i] + L[j]) - j - 1
print(result)

Submission status: Accepted

Solution code:
from bisect import bisect_left
from bisect import bisect_right


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

"""
短いほうから２本固定して条件に合うものをさがす（長いほうから２本固定でもOK）
最長と最短を固定するとややこしくなるから、こういう場合は最長/最短どちらかから固定するほうがいいか
"""


ans = 0
for i in range(N-2):
    a = L[i]
    for j in range(i+1, N-1):
        #b = L[j]
        # そもそもcがaやbより大きいので、下の解法のようにilを求める必要などなく、il=で考えれば良かったんや！
        k = bisect_left(L, a+L[j])
        ans += k - j - 1



"""
ans = 0
for i in range(N):
    for j in range(i+1, N):
        l = L[j] - L[i]
        r = L[j] + L[i]
        #  a < b < c（場合によっては等号を含む）で考えたときの、b - a < cを満たすもの 
        il = bisect_right(L, l, lo=j)
        #  a < b < c（場合によっては等号を含む）で考えたときの、c < a + bを満たすもの
        ir = bisect_left(L, r, lo=j)
        # b - a < cを満たすものがない場合、飛ばす
        if il == N-1:
            break
        
        ans += ir - il - 1
"""

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
from bisect import bisect_right


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

"""
短いほうから２本固定して条件に合うものをさがす（長いほうから２本固定でもOK）
最長と最短を固定するとややこしくなるから、こういう場合は最長/最短どちらかから固定するほうがいいか
"""


ans = 0
for i in range(N-2):
    a = L[i]
    for j in range(i+1, N-1):
        b = L[j]
        # そもそもcがaやbより大きいので、下の解法のようにilを求める必要などなく、il=で考えれば良かったんや！
        k = bisect_left(L, a+b)
        ans += k - j - 1



"""
ans = 0
for i in range(N):
    for j in range(i+1, N):
        l = L[j] - L[i]
        r = L[j] + L[i]
        #  a < b < c（場合によっては等号を含む）で考えたときの、b - a < cを満たすもの 
        il = bisect_right(L, l, lo=j)
        #  a < b < c（場合によっては等号を含む）で考えたときの、c < a + bを満たすもの
        ir = bisect_left(L, r, lo=j)
        # b - a < cを満たすものがない場合、飛ばす
        if il == N-1:
            break
        
        ans += ir - il - 1
"""

print(ans)

Submission status: Accepted

Solution code:
def acinput():
    return list(map(int, input().split(" ")))

import bisect
import numpy as np

N=int(input())
L=acinput()
L=sorted(L)

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

        #print((r-j-1))

        count+=(r-j-1)



print(count)

Submission status: Accepted

Solution code:
N = int(input().strip())
L = [int(str) for str in input().split()]

L.sort()

ans = 0

for a in range(N - 2):
    c = a + 1
    for b in range(a + 1, N - 1):
        while c < N - 1 and L[c + 1] < L[a] + L[b]:
            c += 1
        ans += c - b

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,-1,-1):
    for j in range(i-1,-1,-1):
        temp=L[i]-L[j]
        idx=bisect.bisect_right(L,temp)
        ans+=max(0,j-idx)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import bisect
import itertools


def solve(N: int, L: "List[int]"):
    L.sort()
    L = tuple(L)
    ans = 0
    ans = sum([bisect.bisect_left(L, a+L[j]) - j - 1
               for i, a in enumerate(L[:-1], 1) for j in range(i, N)])
    print(ans)
    return


def main():
    def iterate_tokens():
        for sent in sys.stdin:
            for token in sent.split():
                yield token
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    L = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, L)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
import bisect

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

# l.sort()

# ans = 0
# for a in range(n - 2):
#     for b in range(a + 1, n - 1):
#         ans += bisect.bisect_left(l, l[a] + l[b]) - (a + 1)
# print(ans)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
L = list(map(int,input().split()))
import bisect
 
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 bisect

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n = ni()
l = nl()

l = sorted(l)

ans = 0

for a in range(n):
    fl = 0
    A = l[a]
    for b in range(a+1,n):
        B = l[b]

        idx = bisect.bisect_left(l, A+B)
        ans += max(0,idx-b-1)

print(ans)

Submission status: Accepted

Solution code:
import bisect

N = int(input())
L = input().split()
for i in range(0, N):
  L[i] = int(L[i])
L.sort()
ans = 0
for i in range(0, N-1):
  for j in range(i+1, N):
    a = L[i] + L[j]
    b = bisect.bisect_left(L, a)
    ans += b-j-1
print(ans)

Submission status: Accepted

Solution code:
import bisect

n = int(input())
l = list(map(int, input().split()))
ans = 0
l.sort()
for i in range(n-1, -1, -1):
    a = l[i]
    for j in range(i-1, -1, -1):
        b = l[j]
        c = bisect.bisect_right(l, a-b, lo=0, hi=j)
        ans = ans + j-c
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left#(sorted_list,x)で昇順ソート位置

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):
    s = l[i]+l[j]
    ans += bisect_left(l,s,j+1)-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):
    for j in range(n):
        if i<j:
            k=bisect.bisect_left(l,l[i]+l[j])
            ans+=k-j-1
print(ans)

Submission status: Accepted

Solution code:
import bisect
import sys
input = sys.stdin.readline
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):
    b = ls[j]
    pos = bisect.bisect_left(ls, a+b)
    ans += pos - j - 1
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right


def solve_d(n, l_list):
    res = 0
    l_list_s = sorted(l_list)
    for i in range(1, n - 1):
        b = l_list_s[i]
        for j in range(0, i):
            a = l_list_s[j]
            res += bisect_left(l_list_s, a + b) - (i + 1)

    return res


def solve_d_(n, l_list):
    res = 0
    l_list_s = sorted(l_list)
    h = []
    for i in range(1, n - 1):
        for j in range(0, i):
            heappush(h, l_list_s[i] + l_list_s[j])
        while len(h) > 0:
            a = heappop(h)
            if a > l_list_s[i + 1]:
                heappush(h, a)
                break
        res += len(h)

    return res


def main():
    n = int(input())
    l_list = list(map(int, input().split()))
    res = solve_d(n, l_list)
    print(res)


def test():
    assert solve_d(4, [3, 4, 2, 1]) == 1
    assert solve_d(3, [1, 1000, 1]) == 0
    assert solve_d(7, [218, 786, 704, 233, 645, 728, 389]) == 23


if __name__ == "__main__":
    test()
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left

if __name__ == "__main__":
	N = int(input())
	L = list(map(int, input().split()))
	L.sort()
	# print(L)
	sum = 0
	for a in range(N - 2):
		for b in range(a + 1, N - 1):
			key = L[a] + L[b]
			i = bisect_left(L, key)
			# print(a, b, i, i - b)
			sum += i - b - 1
	print(sum)

Submission status: Accepted

Solution code:
import sys
import bisect

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

print(ans)

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):
    j = i+1
    k = n-1
    while (j < k):
        if l[i] - l[j] - l[k] < 0:
            ans += k - j
            j += 1
        else:
            k -= 1

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

l.sort()
cnt = 0
for i in range(n-1, 1, -1):
    for j in range(i-1, 0, -1):
        x = l[i] - l[j] + 1
        idx = bisect.bisect_left(l, x)
        if j > idx:
           cnt += j - idx
print(cnt)

Submission status: Accepted

Solution code:
import bisect

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

l_s = sorted(l)

for i in range(n-2):
    for j in range(i+1,n-1):
        a = l_s[i] + l_s[j]        
        b = bisect.bisect_left(l_s, a)
        count += max(0,b - j-1)
        
print(count)

Submission status: Accepted

Solution code:
import bisect

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

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect

n = int(input())
ls = [int(elem) for elem in input().split()]
ls = sorted(ls)

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

Submission status: Accepted

Solution code:
import bisect
N = int(input())
L_list = list(map(int,input().split()))
L_list.sort()
ans = 0

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

Submission status: Accepted

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

from bisect import bisect_left


def main():
    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):
            a = l[i]
            b = l[j]
            mx = bisect_left(l, a + b)
            ans += mx - j - 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
L = list(map(int,input().split()))
L.sort(reverse=True)
 
ck = [0]*(N-2)
#print(L)

ans = 0
for i in range(N-2):
  j = i + 1
  k = N - 1
  #print(i,j,k)
  while j < k:
    if L[i]-L[j]-L[k] < 0:
      ans += k-j
      j += 1 
    else:
      k -=1
  
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import bisect


def solve(*args: str) -> str:
    n = int(args[0])
    ln = sorted(list(map(int, args[1].split())))
    s = 0
    for i in range(n-1, 1, -1):
        for j in range(i-1, 0, -1):
            small = bisect.bisect_right(ln, ln[i] - ln[j])
            big = bisect.bisect_left(ln, ln[i] + ln[j], small, j)
            s += big - small

    return str(s)


if __name__ == "__main__":
    print(solve(*[input() for _ in range(2)]))

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):
  a=L[i]
  for j in range(i+1,N-1):
    b=L[j]
    ans+=bisect.bisect_left(L,a+b)-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):
  for j in range(i+1,n):
    temp=l[i]+l[j]
    ans+=(bisect.bisect_left(l,temp)-j-1)
print(ans)

Submission status: Accepted

Solution code:
import sys
import bisect

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

print(ans)

Submission status: Accepted

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

# 昇順にする
L.sort()

import bisect
count=0
for i in range(N):
    for j in range(i+1,N):
        # 2分探索を使うことでn^2*log(n)の探索で終わる,このindexは新たにL[i]+L[j]が挿入できるindexなので、このindex-1が条件を満たす最大のcのindex
        maximum_index = bisect.bisect_left(L,L[i]+L[j])
        count+= maximum_index-1 - j 
print(count)

Submission status: Accepted

Solution code:
from bisect import*
_,l=open(0)
l=sorted(map(int,l.split()))
*e,=enumerate(l)
print(sum(j-bisect(l,a-b,0,j)for i,a in e for j,b in e[:i]))

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, 0, -1):
    for j in range(i - 1, 0, -1):
        ans += max(0, (j - bisect.bisect_right(L, L[i] - L[j])))
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect


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

    print(ans)


if __name__ == "__main__":
    main()

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(N-2):
    for j in range(i+1,N-1):
        s = L[i] + L[j]
        ans += bs.bisect_left(L,s) - j - 1
        # bisect.bisect_left(list, x)
        # はリストにxを挿入できる点を返す
        # すなわち、
        # (val < x for val in list[0:i]) + (val >= x for val in list[i:len(list)])
print(ans)

Submission status: Accepted

Solution code:
from bisect import*
_,l=open(0)
l=sorted(map(int,l.split()))
e=enumerate
print(sum(j-bisect(l,a-b,0,j)for i,a in e(l)for j,b in e(l[:i])))

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):
  a=l[i]
  for j in range(i+1,n-1):
    b=l[j]
    k=bisect.bisect_left(l,a+b)
    cnt+=(k-j-1)
print(cnt)

Submission status: Accepted

Solution code:
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy, copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect_left

def input(): return sys.stdin.readline().strip()


def INT(): return int(input())


def MAP(): return map(int, input().split())


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


sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    n = INT()
    l = LIST()
    l.sort()
    ans = 0
    #print(l)

    for i in range(n-1):
        for j in range(i+1, n):
            low = l[i]
            high = l[j]

            p = bisect_left(l, low + high)
            #print('i:', i, 'j:', j, '→', max(0, p-j-1))
            ans += max(0, p - j - 1)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
arr = list(map(int, input().split()))

arr.sort()
count = 0
for i in range(n-1, 0, -1):
	l, r = 0, i - 1
	while l < r:
		if arr[l] + arr[r] > arr[i]:
			count += r - l
			r -= 1
		else:
			l += 1
print(count)

Submission status: Accepted

Solution code:
N = int(input())
L = [int(i) for i in input().split()]

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

print(ans)

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce
import bisect

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

N=int(input())
L=input()
L=L.split()
L=[int(item) for item in L]
L.sort()
ans=cmb(N,3)
ans2=0
for i in reversed(range(2,N)):
    for j in reversed(range(1,i)):
        a=bisect.bisect_right(L,L[i]-L[j])
#        print('{0}:{1}'.format(a,j))
#        print(a)
        if(a<j):
            ans2+=(j-a)
    

print(ans2)

Submission status: Accepted

Solution code:
import bisect
##################################################################
def main():
    Input = [input() for i in range(2)]
    N = int(Input[0])
    L = list(map(int,Input[1].split()))
    L.sort()
    ans = 0
    for i1 in range(0,N-2):
        a = L[i1]
        for i2 in range(i1+1,N-1):
            b = L[i2]
            ans += bisect.bisect_left(L, a+b) - i2 - 1
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect

N=int(input())
D=[int(x) for x in input().split()]

D.sort()
total=0

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

print(total)

Submission status: Accepted

Solution code:
from bisect import bisect_left
N=int(input())
ll=list(map(int,input().split()))
ll.sort()
ans=0
for i in range(N):
    for j in range(i+1,N):
        if j==i+1:
            delta=bisect_left(ll,ll[i]+ll[i+1],lo=i+1)-i-2
            if delta>0:
                ans+=delta
            in_b=delta+i+1+1
        else:
            if in_b!=N:
                delta=bisect_left(ll,ll[i]+ll[j],lo=in_b)-j-1
            else:
                delta=N-j-1
            if delta>0:
                ans+=delta
            in_b=delta+j+1
print(ans)

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-2): # max
    for j in range(i+1, n-1): # second max
        index = bisect.bisect_left(L[j+1:], L[i]+L[j])
        ans += index
    
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n = I()
L  = sorted(LI())
ret = 0
for i in range(n):
    for j in range(i + 1, n):
        ret += bisect_left(L, L[i] + L[j]) - j - 1

print(ret)

Submission status: Accepted

Solution code:
import bisect

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
L = list(map(int, input().split()))
L.sort()
wa = 0
import bisect
for i in range(N-1,1,-1):
    for j in range(i-1,0,-1):
        diff = L[i]-L[j]
        k = bisect.bisect_right(L, diff)
        wa += j-k if j-k > 0 else 0           
            
print(wa)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

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

Ls.sort()
#print(Ls)

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

Submission status: Accepted

Solution code:
import itertools
import bisect

def read():
    N = int(input().strip())
    L = list(map(int, input().strip().split()))
    return N, L

def solve(N, L):
    L.sort()
    x = 0
    t = [0 for _ in range(N+1)]
    for i in range(N):
        for j in range(i+1, N):
            k = bisect.bisect_left(L, L[i] + L[j])
            if j < k:
                x += (k - j - 1)
    return x

if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))

Submission status: Accepted

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