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:
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):
        ng=N
        ok=j
        while abs(ok-ng)!=1:
            med =(ok+ng)//2
            if L[med]<L[i]+L[j]:
                ok=med
            else:
                ng=med
        ans+=ok-j
print(ans)

Submission status: Accepted

Solution code:
import bisect

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

count = 0

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

Submission status: Accepted

Solution code:
import bisect

N = int(input())
L = [int(l) for l in input().split()]
L.sort()
S = 0
n = 0
S = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        l = L[i] + L[j]
        s = bisect.bisect_left(L, l)
        S += bisect.bisect_left(L, L[i] + L[j]) - j - 1

print(S)

Submission status: Accepted

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

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
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 main():
    N = I()
    L = LI()
    L = sorted(L)
    cnt = 0
    for i in range(N-1):
        a = L[i]
        for j in range(i+1, N-1):
            b = L[j]
            ok = j + 1
            ng = N - 1
            # ensure ok
            if L[ok] >= a + b:
                ok = ng = j
            # ensure ng is not ok
            elif L[ng] < a + b:
                ok = ng = N - 1
            else:
                pass

            while ng - ok > 1:
                m = (ok + ng) // 2
                c = L[m]
                if c < a + b:
                    ok = m
                else:
                    ng = m
            cnt += (ok - j)
    print(cnt)
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):
        k = bisect.bisect_left(L, L[i] + L[j])
        ans += k - (j + 1)

print(ans)

Submission status: Accepted

Solution code:
#coding: utf-8
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):
        idx = bisect_left(L, L[i]+L[j]) - 1 - j
        ans += idx
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
# coding: utf-8
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]
        ans += bisect_left(L, a+b) - 1 - j
print(ans)

Submission status: Accepted

Solution code:
import bisect
# ABC-143-D
N = int(input())
L = sorted(list(map(int, input().split())))
ans = 0

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

Submission status: Accepted

Solution code:
import bisect

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

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

print(ans)

Submission status: Accepted

Solution code:
import bisect


def sort_list():
    _ = input()
    K = [int(x) for x in input().split()]
    ans = 0

    len_k = len(K)
    n_lst = sorted(K)

    for idx in reversed(range(2, len_k)):
        for diff_idx in range(1, idx):
            diff = n_lst[idx] - n_lst[diff_idx]
            insert_index = bisect.bisect_right(n_lst, diff)
            if insert_index < diff_idx:
                # print(n_lst, diff, idx, diff_idx, insert_index)
                ans += diff_idx - insert_index
    print(ans)


if __name__ == "__main__":
    sort_list()

Submission status: Accepted

Solution code:
import bisect

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

Sum = 0
L.sort(reverse=False)

for i in reversed(range(2,N)):
    for j in reversed(range(1,i)):
        hoge = 0
        hoge = j - bisect.bisect(L, L[i] - L[j])
        if hoge < 0:
            hoge = 0
        Sum += hoge

print(Sum)

Submission status: Accepted

Solution code:
import bisect

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

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
X = list(map(int, input().split()))
X.sort()
k=r=0
for i in range(n):
    k = i
    for j in range(i+1, n):
        while k<n and X[i]+X[j]>X[k]:
            k +=1
        r += k-j-1
print(r)

Submission status: Accepted

Solution code:
n = int(input())
xs = map(int, input().split())
xs = sorted(list(xs))
ts = []
for i in range(n):
    for j in range(i+1, n):
        ts.append(xs[i] + xs[j])
ts.sort()
i = 0
j = 0
r = 0
xs.append(10**18)
while True:
    if j == len(xs) or i == len(ts):
        break
    if ts[i] <= xs[j]:
        i += 1
        r += n-j
    else:
        j += 1
print((n*(n-1)*(n-2)//6-r))

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

Submission status: Accepted

Solution code:
import bisect

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

L.sort()

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
L = Counter(int(i) for i in input().split())
maxL = max(L)
key = sorted(L.keys())
val = [L[i] for i in range(1, max(L) + 1)]
acc = [0] * (len(val) + 1)
for i in range(len(val)):
    acc[i + 1] = acc[i] + val[i]
cnt = 0
for a in key:
    cnt += L[a] * (L[a] - 1) * (L[a] - 2) // 6
    cnt += max(acc[min(2 * a - 1, maxL)] - acc[a], 0) * L[a] * (L[a] - 1) // 2
for i in range(len(key) - 1):
    for j in range(i + 1, len(key)):
        a, b = key[i], key[j]
        cnt += L[a] * L[b] * (L[b] - 1) // 2
for i in range(len(key) - 2):
    for j in range(i + 1, len(key) - 1):
        a, b = key[i], key[j]
        cnt += max(acc[min(a + b - 1, maxL)] - acc[b], 0) * L[a] * L[b]
print(cnt)

Submission status: Accepted

Solution code:
import bisect

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

ans = 0
# a <= b <= c

for b in range(1,N-1):
  for c in range(b+1,N):
    # search min(c) with a + b > c <=> a > c - b
    idx = bisect.bisect_left(L,L[c]-L[b]+1)
    #print(L[b],L[c],idx)
    ans += max(b-idx,0) if idx >= 0 else 0 
    #print(idx, ans)
#print(L)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from bisect import bisect_left
N = int(input())
L = sorted([int(i) for i in input().split()])

res = 0

for i in range(N):
    for j in range(i+1, N):
        r = bisect_left(L, L[i]+L[j])
        res += max(r-(j+1), 0)

print(res)

Submission status: Accepted

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

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

print(cnt)

Submission status: Accepted

Solution code:
import bisect
from bisect import bisect_left

n = int(input()) #n行の入力をリストに入れる
l = []
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):
        b=l[j]
        k = bisect_left(l,a+b)
        result += k-j-1

print(result)

Submission status: Accepted

Solution code:
import collections
import math
import operator as op
from functools import reduce

import numpy as np
import math
import bisect


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

    L.sort()
    # M = [L[i] + L[j] for i in range(N) for j in range(i+1, N)]
    # M.sort()

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


            r = bisect.bisect_right(L, a+b-1) 

            ans += r - (j + 1)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections
import math
import operator as op
from functools import reduce

import numpy as np
import math
from bisect import bisect


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

    L.sort()
    # M = [L[i] + L[j] for i in range(N) for j in range(i+1, N)]
    # M.sort()

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

            ans += bisect(L,L[i]+L[j]-1)-j-1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from bisect import bisect_left
def resolve():
    n=int(input())
    L=list(map(int,input().split()))
    L.sort()

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

    print(ans)
resolve()

Submission status: Accepted

Solution code:
N = int(input())
L = list(map(int,input().split()))
ans = 0
L.sort()
from bisect import bisect_left
for i in range(N):
    for j in range(i+1,N):
        #三角形の辺を2つ固定する
        t = L[i] + L[j]
        #配列のindexが返される。
        idx = bisect_left(L,t)
        #2番目に長い辺jより長い、かつ、2辺の和よりも小さい辺の数を求める。
        # t自体を含めないため、-1をしている。
        ans += max(0,idx - j -1)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

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

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

        # k=j+1
        # while k<N:
        #     if l[i]+l[j]>l[k]:
        #         cnt+=1
        #         k+=1
        #     else:
        #         cnt+=0
        #         k+=1
print(cnt)

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int, input().split()))
l.sort()
lt = [n] * (l[n-1] + l[n-2] + 1)
ans = 0
for i in range(l[0]+1):
    lt[i] = 0
length = l[0]
for i in range(1, n):
  if length < l[i]:
    for j in range(length+1, l[i]+1):
      lt[j] = i
    length = l[i]
for i in range(n):
  for j in range(i+1, n):
    right = l[i]+l[j]
    ans += max(0,  lt[right] - (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()
ans = 0
for i in range(n):
  for j in range(i+1, n):
    left = l[j]-l[i]
    right = l[i]+l[j]
    ans += max(0, bisect_left(l, right) - (j+1))
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect
n = int(input())

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

ls.sort()
count = 0
for i in range(n):
    for j in range(i + 1,n):
        t = ls[i] + ls[j]
        index = bisect.bisect_left(ls,t)
        count += max(0,index - j - 1)

print(count)

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, 0, -1):
        A, B = L[i], L[j]
        delta = A-B+1
        idx = bisect.bisect_left(L, delta)
        if idx >= j:
            break
        ans += j-idx

print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
import bisect
import math
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
l = na()

l.sort()

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

Submission status: Accepted

Solution code:
import bisect


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

    l.sort()
    ans = 0

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_right, bisect_left
N = int(input())
L = [int(_) for _ in input().split()]
ans = 0
L.sort()

for n in range(N - 1, -1, -1):
    for m in range(n - 1, -1, -1):
        ans += bisect_left(L, L[n] + L[m]) - n - 1

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left


def main(N, L):
    L.sort()
    ans = 0
    for i in range(0, N-1):
        for j in range(i+1, N):
            r = bisect_left(L, L[i] + L[j])
            ans += r - (j + 1)
    return ans

if __name__ == "__main__":
    N = int(input())
    L = list(map(int, input().split()))
    print(main(N, L))

Submission status: Accepted

Solution code:
import bisect

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

L.sort()
ans = 0

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

print(ans)

Submission status: Accepted

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

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:
import sys
import bisect


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    l = list(map(int, readline().split()))
    l.sort()
    cnt = 0
    for i in range(n):
        for j in range(i + 1, n):
            p = bisect.bisect_left(l, l[j] + l[i])
            cnt += max(0, p - j - 1)
    print(cnt)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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


res = 0
for i in range(N):
    a = L[i]
    for j in range(i + 1, N):
        b = L[j]
        k = bisect.bisect_left(L, a + b)
        res += max(k - (j + 1), 0)
        # print(a, b, k, k - (j + 1))

print(res)

Submission status: Accepted

Solution code:
import bisect
import sys
input = sys.stdin.readline
 
n = int(input())
l = [int(li) for li in input().split(' ')]
l.sort()

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

Submission status: Accepted

Solution code:
import bisect

N = int(input())
L = [int(li) for li in input().split(' ')]
LMAX = 10 ** 3

L.sort()
# print(L)
ans = 0

for i in range(N - 2):
    for j in range(i + 1, N - 1):
        # 1,2番目の棒を長い順に決める
        # 3番目の棒として満たす
        lin = L[i] + L[j]

        ind = bisect.bisect_left(L, lin)
        ans += ind-j-1
print(ans)

Submission status: Accepted

Solution code:
import bisect

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

MAX=L[-1]
count=0
for i in range(N-2):
    for  j in range(i+1,N-1):
        # print(i,j)
        # print(L[i+1:-1])
        minInd=j+1
        # print(minInd)
        
        if L[minInd]> L[i]+L[j]:
            continue
        if MAX<L[i]+L[j]:
            count+=N-1-minInd+1
        else:
            ind = bisect.bisect_left(L, L[i]+L[j])-minInd # number of < a+b
            count+=ind
        
print(count)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect

N = int(input())
L = list(map(int, input().split()))
L.sort()
 
c = 0
for i in range(N-2):
  for j in range(i+1, N-1):
    c += bisect.bisect_right(L, L[i]+L[j]-1) - j - 1


print(c)

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

Submission status: Accepted

Solution code:
N = int(input())
L = list(map(int,input().split()))
ans = 0
L.sort()
lst = [0 for i in range(10**3+1)]
for i in range(N):
    lst[L[i]]+=1
for i in range(10**3+1):
    if i != 0:
        lst[i]=lst[i-1]+lst[i]
for i in range(N-1):
    for j in range(i+1,N):
        p = L[i]+L[j]
        if p-1>=10**3+1:
            ans += lst[10**3]-(j+1)
        else:
            ans += lst[p-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-2):
    for j in range(i,N-1):
        l1 = L[N-1-i]
        l2 = L[N-2-j]
        
        l = N - 2 - j - bisect.bisect_right(L, l1-l2)
        if l >= 0:
            ans += l

print(ans)

Submission status: Accepted

Solution code:
import bisect


def solve(ls) -> int:
  n = len(ls)
  assert(3 <= n <= 2 * 10**3)

  def n_possible_cs(a: int, b: int, first_ic: int) -> int:
    # def bin_search_le_rightmost(s: int, e: int, target: int):
    #   if s == e:
    #     if ls[s] > target:
    #       return None
    #     else:
    #       return s
    #
    #   mid = s + (e - s) // 2
    #
    #   if ls[mid] <= target and (mid + 1 < n and ls[mid + 1] > target):
    #     return mid
    #   elif ls[mid] <= target:
    #     return bin_search_le_rightmost(mid + 1, e, target)
    #   else:
    #     return bin_search_le_rightmost(s, mid, target)

    idx = bisect.bisect_left(ls, a + b, first_ic)
    return 0 if idx == first_ic else idx - first_ic

  ret = 0
  for ia in range(0, n - 2):
    for ib in range(ia + 1, n - 1):
      a, b = (ls[ia], ls[ib])
      x = n_possible_cs(a, b, ib + 1)
      ret += x
  return ret


n = int(input().strip())
ls = [int(l) for l in input().split()]

print(solve(sorted(ls)))

Submission status: Accepted

Solution code:
import bisect

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

L.sort()

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

Submission status: Accepted

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

counts = 0

for i in range(n):
  start, end = 0, i - 1
  while start < end:
    if nums[start] + nums[end] > nums[i]:
      counts += end - start
      end -= 1
    else:
      start += 1
print(counts)

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

        ind = bisect.bisect_left(L, ll)
        ans += ind - 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()))
count = 0
L.sort()

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

print(count)

Submission status: Accepted

Solution code:
#ABC143-D Triangles
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):
        ans += max(bisect_right(L, L[i]+L[j]-1) - j - 1, 0)
        #print([i,j, 100, L[i],L[j], 100, bisect_right(L, L[i]+L[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(len(l) - 2):
    for j in range(i + 1, len(l) - 1):
        ans += bisect.bisect_left(l, l[i] + l[j]) - j - 1
print(ans)

Submission status: Accepted

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

L.sort()

s = 0

ma = L[N-1]
for j in range(N-2):
    ja = L[j]
    for k in range(j+1,N-1):
        ka = L[k]
        # L[i] < L[j]+L[k] となる L[i]の数を求める
        key = ja + ka
        l = k + 1
        r = N - 1
        while r - l > 1:
            m = l + (r - l) // 2
            if L[m] < key:
                l = m
            else:
                r = m
        kka = L[k+1]
        if kka < key <= ma:
            s += l-k
        elif key <= kka:
            s += 0
        else:
            s += N-k-1

print(s)

Submission status: Accepted

Solution code:
import bisect

n = int(input())
L = list(map(int, input().split()))
L.sort()
cnt = 0
for a in range(n - 1):
    for b in range(a + 1, n):
        r = bisect.bisect_left(L, L[a] + L[b])
        l = b + 1
        cnt += r - l
print(cnt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b = LI()
    print(max(0, a - 2 * b))
    return

#B
def B():
    n = II()
    d = LI()
    ans = 0
    for i in range(n):
        for k in range(i+1, n):
            ans += d[i] * d[k]
    print(ans)
    return

#C
def C():
    n = II()
    s = S()
    i = 0
    ans = 1
    for i in range(1, n):
        if s[i - 1] == s[i]:
            continue
        ans += 1
    print(ans)
    return

#D
def D():
    n = II()
    l = LI()
    l.sort()
    ans = 0
    for i in range(n - 1, 0, -1):
        for k in range(i - 1, -1, -1):
            ab = l[i] - l[k]
            c = max(0, k - bisect_right(l, ab))
            ans += c
    print(ans)
    return

#E
def E():
    n, m, l = LI()
    dist = [[inf] * n for i in range(n)]

    for _ in range(m):
        a, b, c = LI_()
        c += 1
        if c > l:
            continue
        dist[a][b] = c
        dist[b][a] = c

    supply = [[n] * n for i in range(n)]
    for k in range(n):
        distk = dist[k]
        for i in range(n):
            if i == k:
                continue
            disti = dist[i]
            distik = dist[i][k]
            for j in range(i + 1, n):
                if distik + distk[j] < disti[j]:
                    disti[j] = distik + distk[j]
                    dist[j][i] = disti[j]

    lis = [[] for i in range(n)]
    for i in range(n):
        for j in range(i + 1, n):
            if dist[i][j] <= l:
                supply[i][j] = 0
                supply[j][i] = 0
                lis[i].append(j)
                lis[j].append(i)

    for i in range(n):
        q = []
        for k in lis[i]:
            heappush(q, (0, k))
        supplyi = supply[i]

        while q:
            time, p = heappop(q)
            for k in lis[p]:
                if supplyi[k] > time + 1:
                    supplyi[k] = time + 1
                    heappush(q, (time + 1, k))

    q = II()
    for _ in range(q):
        s, t = LI_()
        if dist[s][t] == inf:
            print(-1)
            continue
        else:
            print(supply[s][t])
    return


#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
from itertools import combinations
import bisect
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i,j in list(combinations(L,2)):
  if j < 2*i:
    ans += max(0, bisect.bisect_left(L, i+j) - bisect.bisect_right(L, j-i)-2)
  else:
    ans += max(0, bisect.bisect_left(L, i+j) - bisect.bisect_right(L, j-i)-1)
print(ans//3)

Submission status: Accepted

Solution code:
import bisect as b

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

Submission status: Accepted

Solution code:
import bisect
N = int(input())
L0 = list(map(int, input().split()))
L = sorted(L0)
tri = 0
for left in range(N-2):
    for mid in range(left+1, N-1):
        x = bisect.bisect_left(L, L[left]+L[mid])
        tri += x - mid - 1

print(tri)

Submission status: Accepted

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

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

Submission status: Accepted

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

ans=0
for i in range(n-1):
      for j in range(i+1,n):
            idx=bisect.bisect_left(L,L[i]+L[j])
            ans+=idx-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 a_index in range(N):
    for b_index in range(a_index+1, N):
        a_and_b = L[a_index] + L[b_index]
        c_index = bisect.bisect_left(L,L[a_index]+L[b_index])
        ans += max(0, c_index - b_index - 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-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
N=int(input())
L=sorted(list(map(int,input().split())))
ans=0
for i in range(N-2):
  for j in range(N-i-2):        
    ans+=min(N-i-j-2,N-bisect.bisect_left(L,L[-j-1]-L[i]+1)-j-1)
print(ans)