Problem:


Score : 400 points

Problem Statement

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

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

a < b + c

b < c + a

c < a + b

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

Constraints

All values in input are integers.

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

1 \leq L_i \leq 10^3

Input

Input is given from Standard Input in the following format:

N
L_1 L_2 ... L_N

Constraints

Print the number of different triangles that can be formed.

Sample Input 1

4
3 4 2 1

Sample Output 1

1

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

Sample Input 2

3
1 1000 1

Sample Output 2

0

No triangles can be formed.

Sample Input 3

7
218 786 704 233 645 728 389

Sample Output 3

23



Sample input:
4
3 4 2 1


Sample output:
1

Submission status: Accepted

Solution code:
import bisect
 
n = int(input())
l = sorted(list(map(int, input().split())))
count = 0
 
for i in range(n):
    a = l[i]
    for j in range(i+1, n):
        b = l[j]
        ab = a + b
        index_c = bisect.bisect_left(l, ab)#二分探索,abをlの中のどこに挿入するか
        count += index_c - j -1

print(count)

Submission status: Accepted

Solution code:
# coding: utf-8
n = int(raw_input())
L = map(int, raw_input().split())

#昇順にソート
L.sort()

ans = 0



for a in xrange(n-2):
	c = a + 2
	for b in xrange(a+1,n-1):
		while c < n and L[a] + L[b] > L[c]:
			c += 1
		if c > b:
			ans += (c-b-1)
print ans

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import bisect

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

# print(N)
# print(L)

L_sorted = sorted(L)
# print(L_sorted)

count = 0
for i in range(0, N - 2):
    # print(i)
    for j in range(i + 1, N - 1):
        a = L_sorted[i]
        b = L_sorted[j]
        # print(j)
        # for k in range(j + 1, N):
        #     a = L_sorted[i]
        #     b = L_sorted[j]
        #     c = L_sorted[k]
            
        #     if a + b <= c:
        #         break
        #     # print('{}, {}, {}'.format(a, b, c))
        #     count += 1
        
        # print('{}, {},'.format(a, b))
        index = bisect.bisect_left(L_sorted, a + b, i + 1, N)
        # print(index)
        # print((index - 1) - j)
        count += ((index - 1) - j)
        
print(count)

Submission status: Accepted

Solution code:
# D
import sys
import bisect

n = int(input())
l = list(map(int, sys.stdin.readline().strip().split()))

l. sort()
ans = 0
for i in range(len(l) - 1):
    for j in range(i + 1, len(l)):
        a = l[i]
        b = l[j]
        ab = a + b
        right = bisect.bisect_left(l, ab) - 1
        ans += (right - j)

print(ans)

Submission status: Accepted

Solution code:
import sys
import bisect

n = int(input())
l = list(map(int, sys.stdin.readline().strip().split()))

l. sort()
ans = 0
for i in range(len(l)):
    for j in range(i + 1, len(l)):
        a = l[i]
        b = l[j]
        ab = a + b
        right = bisect.bisect_left(l, ab) - 1
        ans += (right - j)

print(ans)

Submission status: Accepted

Solution code:
import bisect

n = int(input())
l = list(int(i) for i in input().split())
list.sort(l)
count = 0

for i in range(n):
    a = l[i]
    for j in range(i+1, n):
        b = l[j]
        ab = a + b
        index_c = bisect.bisect_left(l, ab)
        count += index_c - j -1

print(count)

Submission status: Accepted

Solution code:
import bisect

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

d = 0

for i in range(n - 2):
    for j in range(i + 1, n - 1):
        b = bisect.bisect_left(lis, int(lis[i] + lis[j]))
        d += b - j - 1
print(d)

Submission status: Accepted

Solution code:
import bisect

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

d = 0

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

Submission status: Accepted

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

L.sort()
ans=0
i=0
while i<N-2:
    j=i+1
    k=j+1
    while j<N-1:
        while k<N:
            if L[i]+L[j]<=L[k]:
                ans+=k-j-1
                break
            k+=1
        if k==N:
            ans+=k-1-j
        j+=1
    i+=1
print(ans)

Submission status: Accepted

Solution code:
import bisect

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

for i in range(N-2):
    for j in range(i+1,N-1):
        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(map(int, input().split()))

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

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

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    N = int(input())
    L = sorted(map(int, input().split()))
    ret = 0
    for adx in range(N):
        cdx = adx
        for bdx in range(adx + 1, N):
            while cdx < N and L[cdx] < L[bdx] + L[adx]: cdx += 1
            ret += cdx - (bdx + 1)
    print(ret)

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int, input().split(' ')))
l.sort()
counter = 0
for i in range(n):
    s = i + 2
    for j in range(i+1,n):        
        while (s < n and l[i] + l[j] > l[s]):
            s += 1
        counter += s-j-1
print(counter)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect

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

# solve
ans = 0
L.sort()
for i in range(N):
    for j in range(i + 1, N):
        r = bisect.bisect_left(L, L[i] + L[j])
        l = j + 1
        ans += max(0, r - l)

# output
print(ans)

Submission status: Accepted

Solution code:
import bisect
from sys import exit, stdin
N = int(stdin.readline().rstrip())
L = sorted([int(_) for _ in stdin.readline().rstrip().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())
lis = list(map(int,input().split()))

a = sorted(lis, reverse=True)
c = sorted(lis)
d = 0

for i in range(n):
    for j in range(i + 1, n):
        e = c[:-j-1]
        b = bisect.bisect_right(e, int(a[i]-a[j]))
        d += max(0, len(e) - b)
print(d)

Submission status: Accepted

Solution code:
from bisect import *
if __name__ == '__main__':
    N = int(input())
    L = sorted(map(int, input().split()))
    print(sum(jdx - bisect(L, a - L[jdx], 0, jdx) for idx, a in enumerate(L) for jdx in range(idx)))

Submission status: Accepted

Solution code:
import bisect

def main():
    N = int(input())
    base_list=input().split()
    int_list=[]
    i = 0
    [int_list.append(int(i)) for i in base_list]
    int_list=sorted(int_list)
    anslist=[]
    ans=0
    for index,value in enumerate(int_list):
        for index2,value2 in enumerate(int_list[index+1:]):
            ans+=bisect.bisect_left(int_list,value+value2)-(index+1+index2+1)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def binary_area_search(target_list: list, target_item: int) -> int:
    '''
    @params
    target_list: [1,3,5](ACC)
    target_item: 2

    @return
    return index
    '''
    low = 0
    high = len(target_list) - 1
    while low <= high:
        mid = (low + high) //2
        guess = target_list[mid]
        if guess > target_item:
            if mid == 0:
                return 0
            if target_item > target_list[mid-1]:
                return mid 
            high = mid -1
        else:
            if mid == len(target_list) - 1:
                return None
            if target_list[mid+1] > target_item:
                return mid + 1 
            low = mid + 1
    return None

def main():
    '''
    N^2*logN
    '''
    Ln.sort()
    count = 0
    for a in range(N):
        a_l = Ln[N-a-1]
        for b in range(a+1, N):
            b_idx = N-b-1
            b_l = Ln[b_idx]
            c_threshold = a_l - b_l
            #c_list = Ln[0:N-b-1]
            c_idx = bisect.bisect_right(Ln,c_threshold)
            #c_idx = binary_area_search(c_list,c_threshold)
            if c_idx >= b_idx:
                continue
            count += b_idx - c_idx
    print(count)

def main2():
    '''
    N^2
    '''
    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
    print(count)

def main3():
    '''
    N^2*logN
    '''
    Ln.sort()
    count = 0
    for a in range(N):
        a_l = Ln[N-a-1]
        for b in range(a+1, N):
            b_idx = N-b-1
            b_l = Ln[b_idx]
            c_threshold = a_l - b_l
            #c_list = Ln[0:b_idx+1]
            c_idx = bisect.bisect_right(Ln,c_threshold)
            #c_idx = binary_area_search(c_list,c_threshold)
            if c_idx >= b_idx:
                continue
            count += b_idx - c_idx
    print(count)

main3()

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

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

Submission status: Accepted

Solution code:
N = int(input())
L = list(map(int, input().split()))
L.sort()
answer = 0
for i in range(N-1, 1, -1): # iは辺の最大値
    s = 0 # sは1番短い辺
    l = i-1
    while l > s:
        if L[s] + L[l] > L[i]:
            answer += l - s
            l -= 1
        else:
            s += 1
print(answer)

Submission status: Accepted

Solution code:
N = int(input())
L = list(map(int, input().split()))
L.sort()
answer = 0
for i in range(N-1, 1, -1): # iは辺の最大値
    s = 0 # aは1番短い辺
    l = i-1
    while l > s:
        if L[s] + L[l] > L[i]:
            answer += l - s
            l -= 1
        else:
            s += 1
print(answer)

Submission status: Accepted

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

def binary_area_search(target_list: list, target_item: int) -> int:
    '''
    @params
    target_list: [1,3,5](ACC)
    target_item: 2

    @return
    return index
    '''
    low = 0
    high = len(target_list) - 1
    while low <= high:
        mid = (low + high) //2
        guess = target_list[mid]
        if guess > target_item:
            if mid == 0:
                return 0
            if target_item > target_list[mid-1]:
                return mid 
            high = mid -1
        else:
            if mid == len(target_list) - 1:
                return None
            if target_list[mid+1] > target_item:
                return mid + 1 
            low = mid + 1
    return None

def main():
    '''
    N^2*logN
    '''
    Ln.sort()
    count = 0
    for a in range(N):
        a_l = Ln[N-a-1]
        for b in range(a+1, N):
            b_idx = N-b-1
            b_l = Ln[b_idx]
            c_threshold = a_l - b_l
            #c_list = Ln[0:N-b-1]
            c_idx = bisect.bisect_right(Ln,c_threshold)
            #c_idx = binary_area_search(c_list,c_threshold)
            if c_idx >= b_idx:
                break
            count += b_idx - c_idx
    print(count)

def main2():
    '''
    N^2
    '''
    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
    print(count)
main()

Submission status: Accepted

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

def binary_area_search(target_list: list, target_item: int) -> int:
    '''
    @params
    target_list: [1,3,5](ACC)
    target_item: 2

    @return
    return index
    '''
    low = 0
    high = len(target_list) - 1
    while low <= high:
        mid = (low + high) //2
        guess = target_list[mid]
        if guess > target_item:
            if mid == 0:
                return 0
            if target_item > target_list[mid-1]:
                return mid 
            high = mid -1
        else:
            if mid == len(target_list) - 1:
                return None
            if target_list[mid+1] > target_item:
                return mid + 1 
            low = mid + 1
    return None

def main():
    '''
    N^2*logN
    '''
    Ln.sort()
    count = 0
    for a in range(N):
        a_l = Ln[N-a-1]
        for b in range(a+1, N):
            b_idx = N-b-1
            b_l = Ln[b_idx]
            c_threshold = a_l - b_l
            #c_list = Ln[0:N-b-1]
            c_idx = bisect.bisect_right(Ln,c_threshold)
            #c_idx = binary_area_search(c_list,c_threshold)
            if c_idx >= b_idx:
                continue
            count += b_idx - c_idx
    print(count)

def main2():
    '''
    N^2
    '''
    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
    print(count)
main()

Submission status: Accepted

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

Submission status: Accepted

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

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

res = 0
for i in range(2,n):
    cnt = 0
    for j in range(i):
        p = l[i]-l[j]
        k = bisect.bisect_right(l,p)
        cnt += i-k
        if k <= j:
            cnt -= 1
    res += cnt
print(res//2)

Submission status: Accepted

Solution code:
from bisect import bisect_left

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


a.sort()
count = 0

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

print(count)

Submission status: Accepted

Solution code:
from bisect import *
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):
        s = a[i] + a[j]
        ans += bisect_left(a, s) - j - 1

print(ans)

Submission status: Accepted

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

res = 0
for i in range(n):
    s = i + 1
    e = i + 2
    while True:
        while e < n and lst[i] + lst[s] > lst[e]:
            res += 1
            e += 1
        if e >= n:
            res += (e - s - 1) * (e - s - 2) // 2
            break
        else:
            s += 1
            if e - s -1 > 0:
                res += e - s - 1
            if e == s:
                e += 1
print(res)

Submission status: Accepted

Solution code:
from itertools import combinations
from bisect import bisect_right

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

    L.sort()

    print(sum(bisect_right(L, L[i] + L[j] - 1, lo=j + 1) - (j + 1) for i, j in combinations(range(N), 2)))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect as b
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 += b.bisect_left(l, l[i]+l[j]) - j - 1
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()
def resolve():
    n=int(input())
    L=list(map(int,input().split()))
    L.sort()
    C=[0]*(3001)
    for l in L: C[l]+=1
    for i in range(3000): C[i+1]+=C[i]
    ans=0
    for i in range(n):
        for j in range(i+1,n):
            ans+=C[L[i]+L[j]-1]-j-1
    print(ans)
resolve()

Submission status: Accepted

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


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


if __name__ == '__main__': main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    L=list(map(int,input().split()))
    L.sort()
    ans=0
    for b in range(1,n-1):
        c=b+1
        for a in range(b):
            while(c<n and L[a]+L[b]>L[c]): c+=1
            ans+=c-b-1
    print(ans)
resolve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from bisect import bisect_left

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

A.sort()
ans = 0
for i in range(N):
    a = A[i]
    for j in range(i+1, N):
        # 小さい方2本a,bを決めておく(a < b)
        b = A[j]
        # 条件を満たすcの範囲は b < c < a+b の間
        k = bisect_left(A, a+b)
        ans += k - (j+1)
print(ans)

Submission status: Accepted

Solution code:
k = 31
K = 1<<k
nu = lambda L: int("".join([bin(K+a)[-k:] for a in L[::-1]]), 2)
st = lambda n: bin(n)[2:] + "0"
li = lambda s: [int(a, 2) if len(a) else 0 for a in [s[-(i+1)*k-1:-i*k-1] for i in range(1001)]]

N = int(input())
A = [int(a) for a in input().split()]
C = [0] * 1001
for a in A:
    C[a] += 1
B = li(st(nu(C) ** 2))
for a in A:
    if a <= 500: B[2*a] -= 1
for i in range(1001):
    B[i] //= 2
for i in range(1, 1001):
    C[i] += C[i-1]
ans = N*(N-1)*(N-2)//6
for i in range(1, 1001):
    ans -= (N-C[i-1]) * B[i]
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
from bisect import bisect

N = int(input())
L = sorted([int(i) for i in input().split()])
ans = 0

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

Submission status: Accepted

Solution code:
from itertools import combinations
from bisect import bisect

N = int(input())
L = sorted([int(i) for i in input().split()])
ans = 0

for i, j in combinations(range(N), 2):
    k = bisect(L, L[i]+L[j]-1)
    ans += k - j - 1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
a = sorted(a)
def trian(a):
    n=len(a)
    res = 0
    # 最小辺x
    for x in range(n):
        z=x+2
        # 真ん中の辺y
        for y in range(x+1,n):
            # 最大の辺z
            # nより小さく、二辺の和よりも小さい
            while(z<n and a[x]+a[y]>a[z]):
                z+=1
            # y+1から毎回数えるのではなく、yが増えれば、zも増えるのを利用し、前回の値を保存しておく
            res += z-y-1
    return res
print(trian(a))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# import sys
import bisect

# sys.setrecursionlimit(4100000)


# def inputs(num_of_input):
#     ins = [input() for i in range(num_of_input)]
#     return ins


# def bis_insert(L, target, top=None, bottom=None):
#     if top is None:
#         top = len(L)
#     if bottom is None:
#         bottom = 0

#     while bottom < top:
#         half = (top + bottom) // 2
#         if target > L[half]:
#             bottom = half + 1
#         else:
#             top = half
#     return bottom


def solve(inputs):
    L = string_to_int(inputs)
    L.sort()
    total_count = 0
    for i in range(len(L) - 2):
        for j in range(i + 1, len(L)-1):
            a = L[i]
            b = L[j]
            target = a + b
            # r = bis_insert(L, target)
            r = bisect.bisect_left(L, target)
            total_count += r - j - 1
    return total_count


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    input()
    ret = solve(input())
    print(ret)

Submission status: Accepted

Solution code:
import sys
import bisect

sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def bis_insert(L, target, top=None, bottom=None):
    if top is None:
        top = len(L)
    if bottom is None:
        bottom = 0

    while bottom < top:
        half = (top + bottom) // 2
        if target > L[half]:
            bottom = half + 1
        else:
            top = half
    return bottom


def solve(inputs):
    L = string_to_int(inputs[0])
    L.sort()
    total_count = 0
    for i in range(len(L) - 2):
        for j in range(i + 1, len(L)-1):
            a = L[i]
            b = L[j]
            target = a + b
            # r = bis_insert(L, target)
            r = bisect.bisect_left(L, target)
            total_count += r - j - 1
    return total_count


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    input()
    ret = solve(inputs(1))
    print(ret)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
L = list(map(int,input().split()))
L.sort()
ans = 0
for b in range(N):
    l = b + 1
    r = l
    for a in range(b):
        maxL = L[a] + L[b]
        while r<N and L[r]<maxL: r += 1
        ans += max(0, r-l)
print(ans)

Submission status: Accepted

Solution code:
length = 2010

n = int(input())
L = list(map(int, input().split()))
ans = 0
L.sort()
sum_1 = [0]*length
for i in range(n):
    sum_1[L[i]]+=1
#棒の長さで累積和
for i in range(length-1):
    sum_1[i+1] +=sum_1[i]
for i in range(n-1):
    for j in range(i+1, n):
        a = abs(L[i]-L[j])
        b = L[i]+L[j]
        ans = ans + sum_1[b-1] - sum_1[a]

        if a<L[i] and L[i]<b:
            ans -=1
        
        if a<L[j] and L[j]<b:
            ans -=1
print(ans//3)

Submission status: Accepted

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


N = int(input().split()[0])
l_list = list(map(int, input().split()))
l_list = sorted(l_list)
total = 0

for a_i, a in enumerate(l_list):
    # 一番長い辺を固定
    for b_i, b in enumerate(l_list[:a_i]):
        # 2番目に長い辺を固定
        c_i = bisect.bisect_right(l_list, abs(a - b))
        total += max(b_i - c_i, 0)

ans = total
print(ans)

Submission status: Accepted

Solution code:
from bisect import *

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

cnt = 0

for i in range(n):
    a = l[i]
    for j in range(i+1, n):
        b = l[j]
        lower = max(j+1, bisect_right(l, b-a))
        upper = bisect_left(l, a+b)
        cnt += upper-lower

print(cnt)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

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

Submission status: Accepted

Solution code:
import bisect
N = int(input())
L = list(map(int,input().split()))
L.sort()
ans = 0
for b in range(N):
    l = b + 1
    for a in range(b):
        maxL = L[a] + L[b]
        r = bisect.bisect_left(L, maxL)
        ans += max(0, r-l)
print(ans)

Submission status: Accepted

Solution code:
import bisect

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

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

print(t)

Submission status: Accepted

Solution code:
import bisect

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

t=0
for i in range(n):
  for j in range(i+1,n):
    a = j+1
    b = bisect.bisect_left(l,l[i]+l[j])
    t += b-a if b>a else 0

print(t)

Submission status: Accepted

Solution code:
import bisect

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

li.sort()

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

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)

Submission status: Accepted

Solution code:
N = int(input())
csum = list(0 for _ in range(2000+1))
L = []
for l in map(int,input().split()):
    L.append(l)
    csum[l] += 1
for i in range(1,len(csum)): csum[i] += csum[i-1]
ans = 0
for ib in range(N):
    b = L[ib]
    for ia in range(ib):
        a = L[ia]
        minL, maxL = abs(a-b), a+b
        ans += csum[maxL-1] - csum[minL]
        if minL < a < maxL: ans -= 1
        if minL < b < maxL: ans -= 1
print(ans//3)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
import random  # randome is not available at Codeforces
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
#eps=10**(-10)
#ts=time.time()
#sys.setrecursionlimit(10**6)
input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

n=I()
a=sorted(LI())[::-1]


def solve(a):
    
    s=set()
    for i in a:
        s.add(i)
    s=sorted(list(s))[::-1]
    L=1080
    #L=10000
    k=[0]*(L)
    ak=[0]
    ans=0
    for i in a:
        k[i]+=1
    for i in range(L):
        ak.append(ak[-1]+k[i])
    a1,a2,a3,a4=0,0,0,0
    un=len(s)
    for i in range(un):
        c=s[i]
        if k[c]>=3:
            a1+=k[c]*(k[c]-1)*(k[c]-2)//6
        if k[c]>=2:
            a2+=ak[c]*k[c]*(k[c]-1)//2
        for j in range(i+1,un):
            #show('i,j,s[i],s[j],mm',i,j,'|',s[i],s[j],s[i]-s[j]+1,'|',ak[s[i]-s[j]],ans)
            
            sc=s[j]
            a3+=(1 if 2*sc>c else 0)*k[c]*k[sc]*(k[sc]-1)//2
            if ak[sc]==0:
                break
            mm=c-sc+1
            if mm<0:
                continue
            elif mm>sc:
                continue # break
            else:
                a4+=k[c]*k[sc]*(ak[sc]-ak[mm])
            #show('ans+=',k[sc]*(k[sc]-1)//2+ak[sc]-ak[mm])
    
    ans=a1+a2+a3+a4
    #print(ans)
    return ans,a1,a2,a3,a4

def naive(a):
    b=sorted(a)[::-1]
    n=len(b)
    ans=0
    for i in range(n):
        for j in range(i+1,n):
            for k in range(j+1,n):
                if b[j]+b[k]>b[i]:
                    ans+=1
    return ans

print(solve(a)[0])

Submission status: Accepted

Solution code:
from itertools import *
N = int(input())
csum = list(0 for _ in range(2000+1))
L = []
for l in map(int,input().split()):
    L.append(l)
    csum[l] += 1
csum = list(accumulate(csum))
ans = 0
for ia in range(N-1):
    for ib in range(ia+1,N):
        a, b = L[ia], L[ib]
        minL, maxL = abs(a-b), a+b
        ans += csum[maxL-1] - csum[minL]
        if minL < a and a < maxL: ans -= 1
        if minL < b and b < maxL: ans -= 1
print(ans//3)

Submission status: Accepted

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

import bisect
L = sorted(L)
ans = 0
for i in range(N - 2):
    for j in reversed(range(i + 1, N - 1)):
        k = bisect.bisect_left(L, L[i] + L[j], j)
        ans += k - 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):
  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:
from itertools import *
N = int(input())
csum = list(0 for _ in range(2000+1))
L = []
for l in map(int,input().split()):
    L.append(l)
    csum[l] += 1
csum = list(accumulate(csum))
ans = 0
for ib in range(N):
    for ia in range(ib):
        a, b = L[ia], L[ib]
        minL, maxL = abs(a-b), a+b
        ans += csum[maxL-1] - csum[minL]
        if minL < a and a < maxL: ans -= 1
        if minL < b and b < maxL: ans -= 1
print(ans//3)

Submission status: Accepted

Solution code:
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):
    lf = j
    rf = n
    while rf - lf > 1:
      md = (lf + rf) // 2
      if l[md] < l[i] + l[j]:
        lf = md
      else:
        rf = md
    ans += lf - j
    #print(i, j, ans)
print(ans)

Submission status: Accepted

Solution code:
from itertools import *
N = int(input())
L = list(map(int,input().split()))
csum = list(0 for _ in range(2000+1))
for i in range(N): csum[L[i]] += 1
csum = list(accumulate(csum))
ans = 0
for ib in range(N):
    for ia in range(ib):
        a, b = L[ia], L[ib]
        minL, maxL = abs(a-b), a+b
        ans += csum[maxL-1] - csum[minL]
        if minL < a and a < maxL: ans -= 1
        if minL < b and b < maxL: ans -= 1
print(ans//3)