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 sys
import bisect
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    n = int(input())
    l = 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]) - b - 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import sys
input = sys.stdin.readline


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

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

    print(result)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import sys
input = sys.stdin.readline


def main():
    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.bisect_left(l, l[i] + l[j]) - (j + 1)

    print(result)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left
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_left(l,l[i] + l[j]) - j - 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
Ln = list(map(int,input().split(' ')))
Ln.sort(reverse=True)

count = 0
for a in range(N):
    a_l = Ln[a]
    current_min = N-1
    b = a +1
    while b <= current_min:
        c_idx = current_min
        bc = Ln[b] + Ln[c_idx]
        if a_l < bc:
            count += (current_min - b)
            b += 1
            continue
        current_min -= 1
    '''
    for b in range(a+1, N):
        if b >= current_min:
            break
        for c in range(b+1,N):
            c_idx = current_min
            bc = Ln[b] + Ln[c_idx]
            if a_l < bc:
                count += (current_min - b)
                break
            current_min -= 1
    '''
print(count)

Submission status: Accepted

Solution code:
import bisect

n = int(input())
l_list = list(map(int,input().split()))

l_list.sort()

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

print(count)

Submission status: Accepted

Solution code:
def nibun(a,x):
    return bisect.bisect_left(a, x) #場所返す

import bisect
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
N = I()
ans = int(0)
L = LI()

L.sort()
t = int(0)
for i in range(N):
    for j in range(i+1,N):
        t = L[i] + L[j]
        count =int(0)
        count += nibun(L,t) - (j+1)
        ans += max(count,0)
#        print(i,j,count)

print(ans)

Submission status: Accepted

Solution code:
import bisect
a=int(input())
b=list(map(int,input().split()))
b.sort()
ans=0
for i in range(a):
  for j in range(i+1,a):
    k=bisect.bisect_right(b,b[i]+b[j]-1)
    ans+=k-j-1
print(ans)

Submission status: Accepted

Solution code:
import bisect

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

ans = 0

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

print(ans)

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)
    #        print(c)
    #        ans += c - j - 1

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

    print(ans)

if __name__ == '__main__':
    main()

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):
        insert_index = bisect.bisect_left(l, l[i] + l[j],j) #l[i] + l[j]を挿入できる点を探す。同じ者がlにすでにある時は、一番左になるようにする
        ans += (insert_index - j - 1)

print(ans)

Submission status: Accepted

Solution code:
import bisect

N=int(input())

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

L_sorted=sorted(L)

ans=0

for i in range(2,N):  #2<=i<=N-1
    for j in range(1,i):   #1<=j<=i-1
        MIN=L_sorted[i]-L_sorted[j]+1
        MIN_index=bisect.bisect_left(L_sorted,MIN)
        number_of_indexes=(j-1)-MIN_index+1
        if number_of_indexes>0:
            ans+=number_of_indexes
        
print(ans)

Submission status: Accepted

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

L.sort()

from bisect import*
ans = 0
for i in range(N):
    for j in range(i+1, N):
        a = L[i]
        b = L[j]
        r = bisect_left(L, (a + b))
        l = j + 1
        ans += max(0, r-l)
print(ans)

Submission status: Accepted

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

def f(j, max1, max2):
    L_temp = L[j+1:]
    # print("max1 = ", max1, "max2 = ", max2, L_temp)
    dif = max1 - max2
    left = -1
    right = len(L_temp)
    while right - left != 1:
        temp = (left+right)//2
        if dif < L_temp[temp]:
            left = temp
        else:
            right = temp
    return left+1


ans = 0
max1 = 0
max2 = 0
for i in range(N):
    max1 = L[i]
    for j in range(i+1, N-1):
        max2 = L[j]
        ans += f(j, max1, max2)
        # print("ans = ", ans)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
l_list = list(map(int, input().split()))
l_list.sort()
from bisect import *
ans = 0
for i in range(N):
    for j in range(i + 1, N - 1):
        a = l_list[i]
        b = l_list[j]
        high = a + b
        id1 = bisect_right(l_list, high - 1)
        ans += max(0, id1 - (j + 1))
print(ans)

Submission status: Accepted

Solution code:
import bisect

if __name__ == '__main__':
    n = int(input())
    l = list(map(int,input().split()))

    l = sorted(l)

    answer = 0
    for i in range(0,n):
        for j in range(i+1,n):
            k = bisect.bisect_left(l, l[i]+l[j])
            answer += max(0,k-(j+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) :
  for j in range(i+1,N) :
    result += bisect_left(L,L[i]+L[j]) - (j+1)

print(result)

Submission status: Accepted

Solution code:
N = int(input())
A = sorted([int(a) for a in input().split()])
X = [0] * 1001
for a in A:
    X[a] += 1
for i in range(1, 1001):
    X[i] += X[i-1]

ans = 0
for i in range(N):
    for j in range(i+1, N):
        ans += X[min(A[i]+A[j]-1, 1000)] - (j+1)
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right


def d():
    n = int(input())
    ls = list(map(int, input().split()))
    ls.sort()
    count = 0
    for i in range(n-1, -1, -1):
        for j in range(i-1, -1, -1):
            k = bisect_right(ls, ls[i]-ls[j])
            if j >= k:
                count += j - k

    print(count)


if __name__ == '__main__':
    d()

Submission status: Accepted

Solution code:
#%%
from bisect import bisect_left

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):
        tmp = l[i] + l[j]
        back = bisect_left(l, tmp)
        ans += (back-1) - j
        #print(i, j, back)

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect
from bisect import bisect_left

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

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

print(count)

Submission status: Accepted

Solution code:
from bisect import bisect
from bisect import bisect_left

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

for i in range(len(l)):
	for j in range(i+1, len(l)):
		
		count += bisect_left(l,l[i]+l[j]) - (j+1)

print(count)

Submission status: Accepted

Solution code:
from bisect import bisect
from bisect import bisect_left

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

for i in range(n):
	for j in range(i+1, n):
		c = l[i]+l[j]
		count += bisect_left(l,c) - (j+1)

print(count)

Submission status: Accepted

Solution code:
from bisect import bisect
from bisect import bisect_left

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

for i in range(len(l)):
	for j in range(i+1, len(l)):
		c = l[i]+l[j]
		count += bisect_left(l,c) - (j+1)

print(count)

Submission status: Accepted

Solution code:

def triangle_check(a, b, c):
  if a>b+c:
    return False
  elif b>a+c:
    return False
  elif c>a+b:
    return False
  else:
    return True

def count_triangles(n, sticks):
  assert len(sticks) == n, "lenght of sticks does not match `n`"
  count = 0

  for i in range(len(sticks)-2):
    for j in range(i+1, len(sticks)-1):
      for k in range(j+1, len(sticks)):
        count += triangle_check(sticks[i], sticks[j] , sticks[k])

  return count

def findnumberofTriangles(arr): 
  
    # Sort array and initialize count as 0 
    n = len(arr) 
    arr.sort() 
    count = 0
  
    # Fix the first element. We need to run till n-3 as 
    # the other two elements are selected from arr[i+1...n-1] 
    for i in range(0, n-2): 
  
        # Initialize index of the rightmost third element 
        k = i + 2
  
        # Fix the second element 
        for j in range(i+1,n): 
  
            # Find the rightmost element which is smaller 
            # than the sum of two fixed elements 
            # The important thing to note here is, we use 
            # the previous value of k. If value of arr[i] + 
            # arr[j-1] was greater than arr[k], then arr[i] + 
            # arr[j] must be greater than k, because the array 
            # is sorted. 
            while (k < n and arr[i] + arr[j] > arr[k]): 
                k += 1
  
            # Total number of possible triangles that can be 
            # formed with the two fixed elements is k - j - 1. 
            # The two fixed elements are arr[i] and arr[j]. All 
            # elements between arr[j+1] to arr[k-1] can form a 
            # triangle with arr[i] and arr[j]. One is subtracted 
            # from k because k is incremented one extra in above 
            # while loop. k will always be greater than j. If j 
            # becomes equal to k, then above loop will increment k, 
            # because arr[k] + arr[i] is always greater than arr[k] 
            count += k - j - 1
  
    return count 

if __name__ == "__main__":

  n = int(input())
  sticks = sorted(list(map(int, input().split(" "))))
  # num_triangles = count_triangles(n, sticks)
  num_triangles = findnumberofTriangles(sticks)
  print(num_triangles)

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

print(ans)

Submission status: Accepted

Solution code:

def triangle_check(a, b, c):
  if a>b+c:
    return False
  elif b>a+c:
    return False
  elif c>a+b:
    return False
  else:
    return True

def count_triangles(n, sticks):
  assert len(sticks) == n, "lenght of sticks does not match `n`"
  count = 0

  for i in range(len(sticks)):
    for j in range(i+1, len(sticks)):
      for k in range(j+1, len(sticks)):
        count += triangle_check(sticks[i], sticks[j] , sticks[k])

  return count

def findnumberofTriangles(arr): 
  
    # Sort array and initialize count as 0 
    n = len(arr) 
    arr.sort() 
    count = 0
  
    # Fix the first element. We need to run till n-3 as 
    # the other two elements are selected from arr[i+1...n-1] 
    for i in range(0,n-2): 
  
        # Initialize index of the rightmost third element 
        k = i + 2
  
        # Fix the second element 
        for j in range(i+1,n): 
  
            # Find the rightmost element which is smaller 
            # than the sum of two fixed elements 
            # The important thing to note here is, we use 
            # the previous value of k. If value of arr[i] + 
            # arr[j-1] was greater than arr[k], then arr[i] + 
            # arr[j] must be greater than k, because the array 
            # is sorted. 
            while (k < n and arr[i] + arr[j] > arr[k]): 
                k += 1
  
            # Total number of possible triangles that can be 
            # formed with the two fixed elements is k - j - 1. 
            # The two fixed elements are arr[i] and arr[j]. All 
            # elements between arr[j+1] to arr[k-1] can form a 
            # triangle with arr[i] and arr[j]. One is subtracted 
            # from k because k is incremented one extra in above 
            # while loop. k will always be greater than j. If j 
            # becomes equal to k, then above loop will increment k, 
            # because arr[k] + arr[i] is always greater than arr[k] 
            if(k>j): 
                count += k - j - 1
  
    return count 

if __name__ == "__main__":

  n = int(input())
  sticks = sorted(list(map(int, input().split(" "))))
  # num_triangles = count_triangles(n, sticks)
  num_triangles = findnumberofTriangles(sticks)
  print(num_triangles)

Submission status: Accepted

Solution code:
def answer_143d():    
    n = int(input())
    ls = list(map(int,input().split()))

    ls.sort()
    ans = 0

    for i in range(n-1, 0, -1):
        l = 0
        r = i - 1

        while l < r:
            if ls[l] + ls[r] > ls[i]:
                ans += r - l
                r -= 1
            else:
                l += 1
    print(ans)

if __name__ == '__main__':
    answer_143d()

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-1):
  k = A[i]
  for j in range(i+1, N):
    l = A[j]
    res = bisect.bisect_left(A, k+l)
    ans += res-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(i+1, N):
        lower_bound_i_plus_j = bisect.bisect_left(L, L[i]+L[j])
        ans += lower_bound_i_plus_j - (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 b in range(N):
    for a in range(b):
        ab = L[a] + L[b]
        r = bisect_left(L, ab)
        cnt += r - (b + 1) 
print(cnt)

Submission status: Accepted

Solution code:
from bisect import bisect_left
 
N = int(input())
L = list(map(int, input().split()))
 
L.sort()
 
cnt = 0
 
# 2番目に長い棒bを固定
for b in range(N):
    # bより短い棒aを一つずつ探索
    for a in range(b):
        ab = L[a] + L[b]
        # 二分探索でa+bより短い棒（c<a+bが成り立つc）の範囲を求める
        r = bisect_left(L, ab)
        # cの範囲のうちbの範囲を除外して、cの本数を求める
        cnt += r - (b + 1)
 
print(cnt)

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):
        b = bisect.bisect_left(L,L[i]+L[j])
        cnt += b-j-1
print(cnt)

Submission status: Accepted

Solution code:
import bisect

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

L.sort()

n = 0
# Choose two edges
for i in range(N):
    for j in range(i + 1, N):
        a = L[i] + L[j]
        k = bisect.bisect_left(L, a, lo=j + 1)
        #   assert all(v < a for v in L[:k]) and all(v >= a for v in L[k:])
        # the number of candidates of the third edge
        n += k - (j + 1)

print(n)

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
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):
        ab = L[i]+L[j]
        r = bisect_left(L,ab)
        ans += r-(j+1)
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
from sys import stdin


def main():
    input = lambda: stdin.readline()[:-1]
    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):
            n = bisect_left(L, L[i] + L[j])
            ans += n - (j + 1)
    print(ans)


main()

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left as bl
from bisect import bisect_right as br
n=int(input())
s=sorted(list(map(int,input().split())))
q=0
d=[[""]*(1001)for i in range(1001)]
for i in range(n):
    for j in range(i+1,n):
        x,y=max(s[i],s[j]),min(s[i],s[j])
        if d[x][y]=="":
            c=br(s,x+y-1)-bl(s,x-y+1)-1
            if x-y<y:
                c-=1
            c=max(c,0)
            d[x][y]=c
        q+=d[x][y]
print(q//3)

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

L.sort()

cnt = 0

# 2番目に長い棒bを固定
for b in range(N):
    # bより短い棒aを一つずつ探索
    for a in range(b):
        ab = L[a] + L[b]
        # 二分探索でa+bより短い棒（c<a+bが成り立つc）の範囲を求める
        r = bisect_left(L, ab)
        # cの範囲のうちbの範囲を除外して、cの本数を求める
        cnt += r - (b + 1)

print(cnt)

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

for i in range(n - 2):
    for j in range(i + 1, n - 1):
        lij = l[i] + l[j]
        r = bisect_left(l, lij)
        answer += r - j - 1
        
print(answer)

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

for i in range(n - 2):
    for j in range(i + 1, n - 1):
        lij = l[i] + l[j]
        r = bisect_left(l, lij)
        answer += max(0, r - j - 1)
        
print(answer)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import bisect
import math
from copy import deepcopy
from collections import deque, defaultdict
from operator import mul
from functools import reduce, reduce
sys.setrecursionlimit(20000000)

input = sys.stdin.readline


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

    ans = 0

    for a in range(N):

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

            ans += i - b

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

for b in range(N):
  for a in range(b):
    ab = L[a] + L[b]
    r = bisect_left(L, ab)
    l = b + 1
    
    ans += r-l

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import bisect

def main():
    N = int(input())
    L = list(map(int, input().split()))
    sort_L = sorted(L)
    cnt = 0
    for i in range(N-2):
        for j in range(i+1,N-1):
            tmp = bisect.bisect_left(sort_L,sort_L[i] + sort_L[j])
            if tmp - 1 > j:
                cnt += tmp - j - 1
    print(cnt)

    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
L = list(map(int, input().split()))
 
L.sort()
 
dp = [0]*(1005)
frm = 0
cnt = 0
Lcopy = [1001] + L[::-1]
while Lcopy:
  to = Lcopy.pop()
  for i in range(frm, to):
    dp[i] = cnt
  frm = to
  cnt += 1
  
ans = 0
b = 1
c = 2
while b < N-1:
  sub = L[c] - L[b]

  x = b - dp[sub]
  if x > 0:
    ans += x
  else:
    b += 1
    c = b
    
  c += 1
  if c >= N:
    b += 1
    c = b + 1

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

def main():
# input
    n = int(input())
    l = list(map(int, input().split()))
    l.sort()

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

ans = 0
for i, A in enumerate(L):
    for j, B in enumerate(L[i + 1:], start=i + 1):
        right = bisect_left(L, A + B)
        ans += right - j - 1

print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    l = sorted(LI())
    r = 0
    for i in range(n):
        k = i + 1
        li = l[i]
        for j in range(i+1,n):
            ij = li + l[j]
            while k < n-1 and l[k+1] < ij:
                k += 1
            r += k - j

    return r


print(main())

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    n = int(input())
    ll = list(map(int, input().split()))
    ll.sort()
    ans = 0
    for j, l1 in enumerate(ll[:-1]):
        for i, l0 in enumerate(ll[:j]):
            ans += bisect_left(ll, l0 + l1) - (j + 1)
    print(ans)

main()

Submission status: Accepted

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

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

print (cnt)

Submission status: Accepted

Solution code:
import bisect
import sys

input = sys.stdin.readline


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


n = int(input())
ls = sorted(read_i())
res = 0
for i in range(n - 2):
    x = ls[i]
    for j in range(i + 1, n - 1):
        y = ls[j]
        res += bisect.bisect_left(ls, x + y) - j - 1
print(res)

Submission status: Accepted

Solution code:
import bisect

n = int(input())
l = [int(v) for v in input().split(' ')]
sum = 0
l.sort()
for i in range(n):
    for j in range(n):
        if i < j:
            ab = l[i] + l[j]
            index = bisect.bisect_left(l, ab)
            sum += index - j - 1
print(sum)

Submission status: Accepted

Solution code:
def main():
  n = int(input())
  l = list(map(int, input().split()))
  l.sort()
  l.append(99999999)
  c = 0
  for i in range(n - 2):
      t = i + 2
      for j in range(i + 1, n - 1):
          for k in range(t, n + 1):
              if l[i] + l[j] <= l[k]:
                  t = k
                  break
          if t > j: c += t - j - 1
          if j + 1 == t: t += 1
  print(c)
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
  n = int(input())
  l = list(map(int, input().split()))
  l.sort()
  l.append(99999999)
  c = 0
  for i in range(n - 2):
      t = i + 2
      for j in range(i + 1, n - 1):
          for k in range(t, n + 1):
              if l[i] + l[j] <= l[k]:
                  t = k
                  break
          if t > j: c += t - j - 1
          if j + 1 == t: t += 1
  print(c)
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import sys
import bisect

input = sys.stdin.readline


def main():
    n = int(input())
    l = map(int, input().split())
    # 種類組み合わせ・条件
    l = sorted(l)
    hoge = 0
    for i, a in enumerate(l[:-2], start=1):
        for j, b in enumerate(l[i:-1], start=i):
            index = bisect.bisect_left(l, a + b)
            hoge += index - j - 1
    print(hoge)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def find_triangle_count(d):
    n = len(d)
    d.sort()
    res = 0
    for i in range(n - 2):
        k = i + 2
        for j in range(i + 1, n - 1):
            while k < n and d[i] + d[j] > d[k]:
                k += 1
            if k > j:
                res += k - j - 1
    return res


def solve():
    input()
    input_list = list(map(lambda x: int(x), input().split()))
    print(find_triangle_count(input_list))


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n = int(input())
d = list(map(lambda x: int(x), input().split()))
d.sort()

res = 0

for i in range(n-2):
    k = i + 2
    for j in range(i+1, n-1):
        while k < n and d[i] + d[j] > d[k]:
            k += 1
        if k > j:
            res += k - j - 1

print(res)

Submission status: Accepted

Solution code:
import bisect

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

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

Submission status: Accepted

Solution code:
import bisect
N = int(input())
Data = list(map(int,input().split()))
Data.sort()
ans = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        len3 = Data[i]+Data[j]
        # j番目よりも大きくて、サイズが　len3よりも小さい数
        k = bisect.bisect_left(Data,len3)
        # j番目よりも大きくて k-1番目までが求める数
        if k-1 > j:
            ans += (k-1-j)
print(ans)

Submission status: Accepted

Solution code:
import bisect

N = int(input())
L = sorted([int(x) for x in input().split()])
ans = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        ab = L[i] + L[j]
        r = bisect.bisect_left(L,ab)
        l = j + 1
        ans += r - l

print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np
from numpy.fft import rfft,irfft

N = int(readline())
L = np.array(read().split(),np.int32)

fft_len = 2048

counter = np.bincount(L,minlength=1001)
add = (irfft(rfft(counter,fft_len)**2)+.5).astype(int)

# 同じものを2回使うパターンを除外
add[:2002:2] -= counter
add //= 2

# a+b <= c となる(a,b,c)を除外する

cum = counter.cumsum()
remove = ((N-cum+counter) * add[:1001]).sum()

answer = N*(N-1)*(N-2)//6 - remove
print(answer)

Submission status: Accepted

Solution code:
from sys import stdin
import itertools
import bisect
N = int(stdin.readline().rstrip())
L = [int(x) for x in stdin.readline().rstrip().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]
        k = bisect.bisect_left(L, a+b)
        ans += (k-j-1)
print(ans)

Submission status: Accepted

Solution code:
import sys


def main():
    n = int(sys.stdin.readline().strip())
    l = [int(s) for s in sys.stdin.readline().strip().split()]
    # n = 4
    # l = [1, 2, 3, 4]

    l.sort()

    # [lo, hi)
    # Returns -1 if no valid item
    def b_search(lo, hi, limit):
        while lo + 1 < hi:
            mid = (lo + hi) // 2
            if l[mid] < limit:
                lo = mid
            else:
                hi = mid
        if lo >= hi:
            return -1
        if lo + 1 == hi:
            return lo

    ans = 0
    for i in range(n-2):
        for j in range(i+1, n-1):
            a_plus_b = l[i] + l[j]
            valid_longest_idx = b_search(j, n, a_plus_b)
            ans += valid_longest_idx - j

    print(ans)


main()

Submission status: Accepted

Solution code:
import bisect
n = int(input())
l_li = [int(x) for x in input().split()]
l_li.sort()

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

Submission status: Accepted

Solution code:
from itertools import accumulate, combinations

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

    A = [0] * (2 * 10 ** 3 + 7)
    for l in L:
        A[l] += 1

    S = list(accumulate(A))

    ans = 0
    for b, c in combinations(L, 2):
        l, r = c - b if c > b else b - c, b + c
        ans += S[r - 1] - S[l] - (l < b < r) - (l < c < r)

    print(ans // 3)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate, combinations

N, *L = map(int, open(0).read().split())

A = [0] * (2 * 10 ** 3 + 7)
for l in L:
    A[l] += 1

S = list(accumulate(A))

ans = 0
for b, c in combinations(L, 2):
    l, r = abs(b - c), b + c
    ans += S[r - 1] - S[l] - (l < b < r) - (l < c < r)

print(ans // 3)

Submission status: Accepted

Solution code:
from itertools import accumulate

N, *L = map(int, open(0).read().split())

A = [0] * (2 * 10 ** 3 + 7)
for l in L:
    A[l] += 1

S = list(accumulate(A))

ans = 0
for i in range(N):
    b = L[i]
    for j in range(i + 1, N):
        c = L[j]
        l, r = abs(b - c), b + c
        ans += S[r - 1] - S[l] - (l < b < r) - (l < c < r)

print(ans // 3)