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:
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
import numpy as np
from collections import deque, Counter, defaultdict
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import math
from functools import reduce
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
def lcm_base(a, b):
    return (a * b) // gcd(a, b)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


def main():
  N = int(readline())
  L = list(map(int, readline().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_left(L, a+b)
      ans += (k-(j+1))
  print(ans)
  
  
  
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import sys
n = int(sys.stdin.readline())
l = list(map(int, sys.stdin.readline().split()))
# n = int(input())
# l = list(map(int, input().split()))
l.sort()

def bin_search(x, ok, ng, l):
    while ng - ok > 1:
        mid = (ng + ok) // 2
        if l[mid] < x:
            ok = mid
        else:
            ng = mid
    return ok + 1

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

Submission status: Accepted

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

def bin_search(x, ok, ng, l):
    while ng - ok > 1:
        mid = (ng + ok) // 2
        if l[mid] < x:
            ok = mid
        else:
            ng = mid
    return ok + 1

ans = 0
for i in range(n - 2):
    for j in range(i + 1, n - 1):
        ans += bin_search(l[i] + l[j], -1, n - j - 1, l[j + 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

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

L.sort()
ans = 0

for i in range(1,N-1):
    upper = N-1
    for j in reversed(range(0,i)):
        sum = L[i] + L[j]

        if upper == N :
            upper = N-1

        while upper > i and sum <= L[upper]:
            upper -= 1
        ans += upper-i

print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from bisect import bisect_left
N = int(input())
#S = input()[:-1]
#N,M = map(int,input().split())
#S,T = map(str,input().split())
A = list(map(int,input().split()))
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
d = 0
A.sort()
for i in range(N-2):
    for j in range(i+1,N-1):
        s = A[i]+A[j]
        dex = bisect_left(A,s)
        if dex > j:
          d += dex -j -1
print(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 a in range(n-2):
    for b in range(a+1,n-1):
        ans+=max(0,bisect_left(l, l[a] + l[b])-b-1)
        
        
print(ans)

Submission status: Accepted

Solution code:
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):
        a = L[i]
        for j in range(i+1, N-1):
            k = bisect_left(L, a + L[j])
            ans += (k - (j + 1))

    print(ans)

    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
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):
        a = L[i]
        for j in range(i+1, N-1):
            k = bisect_left(L[j+1:], a + L[j])
            ans += k

    print(ans)

    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left

def main():
    N = int(input())
    L = list(map(int, input().split()))
    
    L = sorted(L)
    ans = 0
    for i in range(N-2):
        a = L[i]
        for j in range(i+1, N-1):
            k = bisect_left(L[j+1:], a + L[j])
            ans += k

    print(ans)

    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
l=sorted(map(int,input().split()))
from bisect import *
print(sum(bisect_left(l,l[i]+l[j])-i-1 for i in range(n) for j in range(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, -1, -1):
    for j in range(i-1, -1, -1):
        ans += (n-1-i) - (n - bisect.bisect_left(l,l[i]+l[j]))

print(ans)

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

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from bisect import bisect_left
INF = float("inf")
N = int(input())
L = list(map(lambda x:int(x),input().split())) + [INF]
L.sort()
cnt = 0
for i in range(N-1):
    a = L[i]
    for j in range(i+1,N):
        b = L[j]
        c = bisect_left(L,a+b)
        cnt += max(0,c-j-1)
print(cnt)

Submission status: Accepted

Solution code:
import bisect
N=int(input())
L=sorted(map(int,input().split()))
cnt=0
for i in range(N):
    for j in range(i):
        a=L[i]
        b=L[j]
        right=a+b
        left=abs(a-b)
        rind=bisect.bisect_left(L,right)
        lind=bisect.bisect_right(L,left)
        res=rind-lind
        if(left<a<right):
            res-=1
        if(left<b<right):
            res-=1
        cnt+=res
print(cnt//3)

Submission status: Accepted

Solution code:
import sys
import bisect

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

count = 0

for i in range(N - 2):
    for j in range(i + 1, N - 1):
        c = bisect.bisect_left(L, L[i]+L[j])
        if c > j:
            count += c - j - 1
        else:
            pass
        
print(count)

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

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left
N=int(input())
L=list(map(int,input().split()))
L.sort()
total = 0
for i in range(N):
  for j in range(i + 1, N):
    a = L[i] + L[j]
    total += max(bisect_left(L, a) - j - 1, 0)

print(total)

Submission status: Accepted

Solution code:
N = int(input())
L = list(map(int,input().split()))
L.sort()
M = L[-1]
d = [0] * (2*M+1)
cnt = 0
num = 0
for i in range(N-1):
    cnt += 1
    for j in range(L[i], L[i+1]):
        d[j] = cnt
cnt += 1
for i in range(L[N-1], 2*M+1):
    d[i] = cnt
ans = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        num = L[i] + L[j]
        if num <= M:
            ans += d[num-1] - j - 1
        else:
            ans += N-1-j
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect

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

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

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
n=I()
ls=sorted(LI(),reverse=True)
trans=0
for i in range(n-2):
    answer=0
    for j in range(i+1,n-1):
        l1=ls[i]
        l2=ls[j]
        l,r = j,n
#あえて左右一つ分ずつ広く取る
        while l+1 < r:
#この条件で探索の終点がうまく定められる
            mid = (l+r)//2
            if l1<l2+ls[mid]:
                l = mid
            else:
                r = mid
        ansij=l-j
        #print(ansij)
        answer+=ansij
    trans+=answer
print(trans)

Submission status: Accepted

Solution code:
import bisect

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

SL = sorted(L)
ans = 0
for i in range(N):
  if i+1 == N-1:
    break
  a = SL[i]
  for j in range(i+1, N):
    b = SL[j]
    c_max = bisect.bisect_left(SL, a+b)
    ans += c_max - (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):
    #small = bisect.bisect_left(L, L[j]-L[i])
    large = bisect.bisect_left(L, L[j]+L[i])    
    #print(i,j,L[i],L[j],"  ",L[j]-L[i],L[j]+L[i],small,large)
    ans += max(large-j-1,0)    

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
n = int(input())
l = [int(x) for x in input().split()]
l.sort()
x = 0

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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc143/tasks/abc143_d
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline
n = int(input()) # 入力が1つ
# map(int, input().split()) # 入力が複数
L = [int(i) for i in input().split()]
L.sort()
ans = 0
for i in range(n):
    for j in range(i + 1, n):
        a, b = L[i], L[j]
        ans += bisect_left(L, a + b) - 1 - j
print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc143/tasks/abc143_d
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline
n = int(input()) # 入力が1つ
# map(int, input().split()) # 入力が複数
L = [int(i) for i in input().split()]
L.sort()
pairs = []
for i in range(n):
    for j in range(i + 1, n):
        pairs.append((i, j))

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

Submission status: Accepted

Solution code:
N=int(input())
L=list(map(int,input().split()))
L.sort(reverse=1)
cnt=0
for i in range(N-2):
    for k in range(i+1,N-1):
        num=L[i]-L[k]
        left=k+1
        right=N-1
        while left<=right:
            mid=(left+right)//2
            if num<L[mid]:
                left=mid+1
            else:
                right=mid-1
        cnt+=left-(k+1)
print(cnt)

Submission status: Accepted

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

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

Submission status: Accepted

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

L.sort()
import bisect
ans = 0
for i in range(n-2):
    b = L[i]
    for j in range(i+1, n-1):
        c = L[j]
        p = bisect.bisect_left(L, b+c)
        #print(b, c, j, p, p-j-1)
        ans += max(p-j-1, 0)
print(ans)

Submission status: Accepted

Solution code:
import bisect

n = int(input())
l = [int(i) for i in input().split()]
l.sort()

cnt = 0
for a in range(n):
    for b in range(a+1, n):
        c = bisect.bisect_left(l, l[a] + l[b])
        if c > b:
            cnt += c - b - 1
print(cnt)

Submission status: Accepted

Solution code:
from bisect import bisect_left

N=int(input())
L=list(map(int,input().split()))
M=sorted(L)
#print(M)
ans=0
for i in range(N):
	for j in range(i+1,N):
		k=bisect_left(M,M[i]+M[j])
		#print(k,max(0,k-(j+1)))
		ans+=max(0,k-(j+1))
print(ans)

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

Submission status: Accepted

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

from bisect import bisect_left

ans = 0
# a < b < c
for a in range(N):
    for b in range(a+1, N):
        right = bisect_left(L, L[a] + L[b])
        # [b+1, right)
        ans += max(0, right - (b + 1))

print(ans)

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):
        bc = L[i]+L[j]
        a = bisect_left(L,bc)
        ans+= a-j-1
print(ans)

Submission status: Accepted

Solution code:
import bisect
N = int(input())
l = [int(i) for i in input().split()]
count = 0
l_new = sorted(l)
for i,a in enumerate(l_new):
    for j,b in enumerate(l_new[i+1:],start = i+1):
        left = bisect.bisect_right(l_new,abs(a-b))
        right = bisect.bisect_left(l_new,a + b)
        count += right - left
        
        if left <= i < right:
            count -= 1
        if left <= j < right:
            count -= 1
        
print(count//3)

Submission status: Accepted

Solution code:
import bisect
# from collections import Counter, deque
# from copy import copy, deepcopy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np
# from operator import xor
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline

def resolve():
    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):

            val=bisect.bisect_left(L,L[i]+L[j])
            cnt+=val-j-1

    print(cnt)

resolve()

Submission status: Accepted

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

ans=0
from bisect import bisect_right
for i in range(N-1,-1,-1):
    li = L[i]
    for j in range(i-1,-1,-1):
        lj = L[j]
        k = bisect_right(L, li-lj)
        ans += max(0, j-k)
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
a=[]
for i in range(n-2):
    for j in range(i+1,n-1):
        t=l[i]+l[j]
        cnt=bisect_left(l,t)
        ans+=cnt-j-1
print(ans)

Submission status: Accepted

Solution code:
n= int(input())
l = list(map(int,input().split()))
l.sort()
def ok(a,b,c):
    return a < b+c and b < a+c and c < a+b
ans = 0
for i in range(n):
    for j in range(i+1,n):
        e1 = l[i]
        e2 = l[j]
        top = n
        bot = j
        while top - bot > 1:
            mid = (top+bot)//2
            if ok(l[mid],e1,e2):bot = mid
            else:top  = mid
        
        ans += top-j-1
print(ans)

Submission status: Accepted

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

def valid(i, j ,x):
    if x < i + j:
        return True
    else:
        return False

ans = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        # L[j]より大きくて、L[i] + L[j]より小さい棒を選ぶと三角形を作ることができる。
        insert_point = bisect.bisect_left(L, L[i] + L[j])
        ans += insert_point - j - 1
print(ans)

Submission status: Accepted

Solution code:
import bisect

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

for a in range(n):
    for b in range(a):
        over_c = l[a] + l[b]
        over_c_index = bisect.bisect_left(l,over_c)
        quantity = over_c_index - a - 1
        ans += max(quantity,0)
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    L = [int(i) for i in input().split()]
    L.sort()

    def is_ok(i, j, k):
        if L[j]+L[k] > L[i]:
            return True
        else:
            return False

    def binary_search_meguru(i, j):
        ng = -1
        ok = j
        while abs(ok - ng) > 1:
            mid = ng + (ok - ng) // 2
            if is_ok(i, j, mid):
                ok = mid
            else:
                ng = mid
        return ok
    ans = 0
    for i in range(2, N):
        # i番目を最長辺とする
        for j in range(i):
            k = binary_search_meguru(i, j)
            # print(i, j, k)
            ans += j-k
    print(ans)


if __name__ == '__main__':
    main()

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

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

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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):
        l = L[i] + L[j]
        k = bisect_left(L, l)
        ans += max(0, k - j - 1)
print(ans)

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    N = 10**6+1
    bit = [0]*(N+1)
    def add(i):
        while i <= N:
            bit[i] += 1
            i += i&-i
    def sum(i):
        res = 0
        while i:
            res += bit[i]
            i -= i&-i
        return res

    n = I()
    l = LI()
    l.sort()
    ans = 0
    s = []
    k = 0
    for i in range(n):
        li = l[i]
        ans += k-sum(li)
        for j in range(i):
            add(li+l[j])
            k += 1
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
mod = 10**9 + 7

def main():
    N = iip(listed=False)
    L = iip(True)
    L.sort()

    ret = 0
    for i in range(N):
        for j in range(i+1, N):
            minl = L[j]-L[i]
            maxl = L[j]+L[i]

            left = searchsorted(L, minl, "right")
            left = max(j+1, left)

            right = searchsorted(L, maxl, "left")

            #print(L[i], L[j], left, right)

            #print(i, j, left, right)
            ret += (right-left)
    print(ret)




#####################################################ライブラリ集ここから

def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    while r-l > 1:
        x = (l+r)//2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        return r
    if side == "right":
        return l+1



def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <=0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n-r+1, n+1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r+1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        #print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod-2)

def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p//2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p-1)) % mod


if __name__ == "__main__":
    main()

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

print(cnt)

Submission status: Accepted

Solution code:
import collections
N=int(input())
L=list(map(int,input().split()))
l=[]
L.sort()
lis=[0]*(max(L)+1)
cnt=0
ans=0
c=collections.Counter(L)
values=list(c.values())	#aのCollectionのvalue値のリスト(n_1こ、n_2こ…)
key=list(c.keys())	#先のvalue値に相当する要素のリスト(要素1,要素2,…)
l1=0
l2=0
mi=0
ma=0
le=0
for i in range(len(key)):
    l.append([key[i],values[i]])#lは[要素i,n_i]の情報を詰めたmatrix
l.sort(key=lambda x:x[0])
#print(lis,L)
for i in range(max(L)+1):
    #print(cnt)
    cnt=cnt+c[i]
    lis[i]=cnt
for i in range(len(L)-1):
    for j in range(i+1,len(L)):
        l1=L[i]
        l2=L[j]#l1<=l2
        ma=min(l1+l2-1,L[len(L)-1])
        mi=max(l2-l1+1,L[0])
        le=lis[ma]-lis[mi-1]
        if mi<=l1<=ma:
            le=le-1
        if mi<=l2<=ma:
            le=le-1
        #print(l1, l2,c[l1],c[l2],ma,mi,le)
        ans=ans+max(le,0)
print(ans//3)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

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

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 k in range(i+1,N):
        ans+=bisect.bisect_left(L,L[i]+L[k])-k-1
print(ans)

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):
    A = L[i] + L[j]
    highbound = bisect_left(L, A)
    ans += highbound - j - 1    
print(ans)

Submission status: Accepted

Solution code:
### a<=b<=cととることとし、a,bを固定すると
### cは　c<a+b
from bisect import bisect_left
def main():
    N = int(input())
    lst = list(map(int, input().split()))
    sor = sorted(lst)
    res = 0
    for i in range(N):
        for j in range(i+1, N):##ここでa<=bを満たしている
            ab = sor[i] + sor[j]
            highbound = bisect_left(sor, ab)
            res += highbound - j - 1
    print(res)
main()
### ライブラリを使おう！！！

Submission status: Accepted

Solution code:
### a<=b<=cととることとし、a,bを固定すると
### cは　c<a+b
from bisect import bisect_left
N = int(input())
lst = list(map(int, input().split()))
sor = sorted(lst)
res = 0
for i in range(N):
    for j in range(i+1, N):##ここでa<=bを満たしている
        ab = sor[i] + sor[j]
        highbound = bisect_left(sor, ab)
        res += highbound - j - 1
print(res)
### ライブラリを使おう！！！

Submission status: Accepted

Solution code:
#python3
from bisect import bisect_left
def main():
    n = int(input())
    L = [int(i) for i in input().split()]
    L.sort()
    ans = 0
    for i in range(n):
        for j in range(i+1, n):
            ab = L[i]+L[j]
            r = bisect_left(L, ab)
            l = j+1
            ans += r-l
    print(ans)
main()

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right  # return index

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

ans = 0
for i in range(N):
    for j in range(i+1, N):
        tmp = L[i]+L[j]  # tmpはこの値より短くなくてはいけない

        ### ここから下は二分探索
        ix = bisect_left(L, tmp)
        ans += ix-(j+1)

print(ans)

Submission status: Accepted

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
L = lr()
L.sort()
answer = 0
for i in range(N-1, -1, -1):
    # iが一番大きい辺
    x = L[i]
    left = 0
    right = i - 1
    while left < right:
        if L[left] + L[right] <= x:
            left += 1
            continue
        answer += (right - left)
        right -= 1

print(answer)

Submission status: Accepted

Solution code:
def binsearch(l, r, fn, i, j):
    while r - l > 1:
        m = (l + r) // 2
        if fn(m, i, j):
            l = m
        else:
            r = m
    return l

def main():
    N = int(input())
    L = list(map(int, input().split()))
    L.sort()
    def fn(m, i, j):
        a = L[m]
        b = L[i]
        c = L[j]
        if a < b + c and b < c + a and c < a + b:
            return True
        return False
    r = 0
    for i in range(N-2):
        for j in range(i+1, N-1):
            if fn(j+1, i, j):
                r += binsearch(j+1, N, fn, i, j) - j
    return r
print(main())

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
L = lr()
L.sort()
answer = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        index = bisect_left(L, (L[i]+L[j]))
        answer += index - j - 1

print(answer)

Submission status: Accepted

Solution code:
import bisect

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

    num_list.sort()

    ans = 0

    for i in range(n-2):
        for j in range(i+1,n-1):
            tmp = bisect.bisect_left(num_list, num_list[i]+num_list[j])
            ans += tmp - 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 in range(0, N):
    for j in range(i+1, N):
        ans += bisect_left(L, L[i]+L[j])-j-1
print (ans)

Submission status: Accepted

Solution code:
#template
def inputlist(): return [int(j) for j in input().split()]
from collections import Counter
#template
#issueから始める
N = int(input())
L = inputlist()
L.sort()
ans = 0
from bisect import bisect_left
for i in range(N-2):
    for j in range(i+1,N-1):
        lia = L[j+1:]
        indexa = bisect_left(lia,L[i]+L[j])
        ans += indexa
print(ans)

Submission status: Accepted

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

import bisect

L_list = sorted(L_list)
 
ans = 0
for a_index in range(0, N):
    for b_index in range(a_index+1, N):
        a = L_list[a_index]
        b = L_list[b_index]
        c_right_index = bisect.bisect_left(L_list, a+b)
        if c_right_index > b_index:
            ans += c_right_index - b_index - 1
        else:
            pass

print(ans)

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import bisect

def solve():
    N = int(input())
    Ls = list(map(int, input().split()))
    Ls.sort()

    # O(N^2 * logN)の全探索で解く
    ans = 0
    for a_i in range(N):
        for b_i in range(a_i+1, N):
            c_i = bisect.bisect_left(Ls, Ls[a_i]+Ls[b_i])
            if c_i > b_i:
                ans += c_i - b_i - 1
            else:
                pass

    print(ans)

if __name__ == "__main__":
    solve()