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: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import 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)]


def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]


def sosu(x):
    for i in range(2, int(sqrt(x)+1)):
        if x % i == 0:
            return False
    return True


mod = 1000000007
inf = float('INF')


def A():
    A, B = LI()
    ans = A-2*B
    if ans > 0:
        print(ans)
    else:
        print(0)
    return

# B


def B():
    N = II()
    d = LI()
    ans = 0
    for i in range(N):
        for x in range(i+1, N):
            ans += d[i]*d[x]
    print(ans)

    return

# C


def C():
    N = II()
    S = input()
    c = 0
    count = 0
    for i in S:
        if i != c:
            count += 1
        c = i
    print(count-1)

    return

# D


def D():
    N = II()
    L = LI()
    L.sort()

    L2 = deque(L)
    count = 0
    for i in range(N-2):
        L2.popleft()
        L3 = list(L2)
        L3 = deque(L3)

        for j in range(i+1, N-1):
            L3.popleft()
            if L3 == deque([]):
                break
            p = L[i]+L[j]

            if L3[0] >= p:
                continue
            #Lk = filter(lambda x: x % 2 == 1, L2)
            Lk = [x for x in L3 if p > x]
            count += sum(x < p for x in L3)

            
        if len(L2) == 2:
            break
    print(count)

    return

# E


def E():
    N, M = LI()
    bit_max = 1 << N
    dp = [[inf for i in range(bit_max)] for j in range(M+1)]
    dp[0][0] = 0

    for i in range(M):
        a, b = LI()

        c = LI()
        bit = 0

        for d in c:
            bit |= 1 << (d-1)

        for w in range(bit_max):

            t = w | bit
            cost = dp[i][w] + a

            dp[i+1][t] = min(dp[i+1][t], cost)

            dp[i+1][w] = min(dp[i][w], dp[i+1][w])

    print(-1) if dp[-1][-1] == inf else print(dp[-1][-1])

    return

# F


def F():
    N, M = LI()

    value = [0] * M
    power = [0] * M
    for i in range(M):
        a, b = LI()
        value[i] = a
        c = LI()
        L = ['0'] * N
        for k in c:
            L[k - 1] = '1'
        bint = ''.join(L)
        power[i] = int(bint, 2)
    bint = ''.join(list(['1'] * N))
    dp = [inf] * (int(bint, 2)+1)
    t = 0
    cost = 0

    dp[0] = 0
    for s in range(int(bint, 2) + 1):
        for i in range(M):
            t = s | power[i]
            cost = dp[s] + value[i]
            dp[t] = min(dp[t], cost)
    print(-1) if(dp[-1] == inf) else print(dp[-1])

    return

    # you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")


def solution(S):
    # write your code in Python 3.6
    import math

    vowels = "AIUEO"
    count = 0
    consonants = 0
    newC = []
    newV = []

    for i in S[:-1]:
        if i in vowels:
            count += 1
            newV.append(i)
        else:
            consonants += 1
            newC.append(i)

    if consonants < count or consonants - 2 > count:
        return 0

    a = math.factorial(len(set(newC))) * math.factorial(len(set(newV)))
    return a

    pass


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

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
from itertools import combinations

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

ans = 0
for e1, e2, e3 in combinations(L, 3):
    if e1 < e2 + e3 and e2 < e1 + e3 and e3 < e1 + e2:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve(n, l):
    l = sorted(l)
    
    ans = 0
    for i in range(0, n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                a = l[i]
                b = l[j]
                c = l[k]
                if a < b + c and b < a + c and c < a + b:
                    ans += 1
                else:
                    break
    return ans
 
n = int(input())
l = list(map(int, input().split()))
 
ans = solve(n, l)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve(n, l):
    l = sorted(l)
    
    ans = 0
    for i in range(0, n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                a = l[i]
                b = l[j]
                c = l[k]
                if a < b + c and b < a + c and c < a + b:
                    ans += 1
                else:
                    break
    return ans

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

ans = solve(n, l)
print(ans)

Submission status: Time Limit Exceeded

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

L.sort()

count = 0
i = 0
while i < N -2:
	j = i +1
	while j < N -1:
		k = j +1
		while k < N:
			if L[i] + L[j] > L[k]:
				count += 1
			else:
				break
			k += 1
		j += 1
	i += 1
	
print(count)

Submission status: Time Limit Exceeded

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

L.sort()

count = 0
i = 0
while i < N -2:
	j = i +1
	while j < N -1:
		k = j +1
		while k < N:
			if L[i] + L[j] > L[k]:
				count += 1
			k += 1
		j += 1
	i += 1
	
print(count)

Submission status: Time Limit Exceeded

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

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):
        # 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(count)

Submission status: Time Limit Exceeded

Solution code:
N=raw_input()
LN=raw_input().split()

n = int(N)
ln = [int(i) for i in LN]

c = []
for i in range(n):
    for j in range(i):
        for k in range(j):
            c.append([i,j,k])


r = []
for i in c:
    x, y, z = i
    a = ln[x]
    b = ln[y]
    c = ln[z]
    if not a < b + c:
        continue
    if not b < c + a:
        continue
    if not c < a + b:
        continue
    r.append(i)

print len(r)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = list(map(int,input().split(" ")))
l.sort()
cnt = 0 
def search(arr,target,start,last):
#    print(target,start,last)
    if len(arr[start:last]) == 1 or start == last:
        if arr[start] > target:
            return start
        else:
            return -1
    mid = (last - start)//2 + start
    if arr[mid] <= target:
        return search(arr,target,mid,last)
    else:
        return search(arr,target,start,mid)
    return -1

for i in range(0,n-2):
    a = l[i]
    for j in range(i+1,n-1):
        b = l[j]
        target = a - b 
        f1 = search(l,target,j+1,n)
 #       print(f1)
        if f1 == -1: 
            continue
        target = b - a 
        f2 = search(l,target,f1,n)
  #      print(f2)
        if f2 == -1: 
            continue
        target = a 
        for k in range(f2,n):
            if a + b > l[k]:
                cnt+=1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
L = list(map(int,input().split()))
L = sorted(L)
ans = 0
# print(L)

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

Submission status: Time Limit Exceeded

Solution code:
n = input()
l = input().split(" ")
l = [int(i) for i in l]

l.sort(reverse = True)

res = 0

for i in list(range(0, len(l) - 2)):
  e1 = l[i]
  for j in list(range(i+1, len(l) - 1)):
    e2 = l[j]
    e3can = l[j+1:]
    res = res + len([k for k in e3can if k > e1 - e2])

print(res)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = [int(i) for i in input().split()]
s = 0
for i in range(n - 2):
  for j in range(i + 1, n - 1):
    for k in range(j + 1, n):
      s += (l[i] + l[j] > l[k]) * (l[j] + l[k] > l[i]) * (l[k] + l[i] > l[j])
print(s)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4000000)

n = int(input())
L = list(map(int, input().split()))
L.sort(reverse=True)

cnt = 0
for i in range(n-2):
    a = L[i]
    for j in range(i+1, n-1):
        b = L[j]
        if a >= 2*b:
            break
        for k in range(j+1, n):
            c = L[k]
            if c >= a+b:
                break
            if (a < (b+c)) & (b < (c+a)) & (c < (a+b)):
                cnt += 1
                
print(cnt)

Submission status: Time Limit Exceeded

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

L.sort()
ans = 0
mem_k = 2
for i in range(N-2):
    for j in range(i+1, N-1):
        for k in range(mem_k, N):
            if L[k] >= L[i] + L[j]:
                ans -= 1
                break
        ans += k - j
        mem_k = max(k, j+1)
    mem_k = i + 2

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def lowerBound(nums, target):
    if nums[-1] < target:
        return -1
    lp = 0
    rp = len(nums) - 1
    mp = lp + rp >> 1
    while lp <= rp:
        mp = lp + rp >> 1
        if nums[mp] == target:
            #print("Solved\nmp: ", mp)
            return mp
        if nums[mp] < target:
            lp = mp + 1
        else:
            rp = mp - 1
    #print("Not found\nmp: ", mp)
    return mp if target < nums[mp] else -1

if __name__ == '__main__':
    N = int(input())
    L = [int(l) for l in input().split()]
    L.sort()
    #print("sorted list", L)
    ret = 0
    for idx in range(len(L) - 1, 1, -1):
        for jdx in range(idx - 1, 0, -1):
            c = L[idx] - L[jdx] + 1
            ldx = lowerBound(L[:jdx], c)
            #print("a: ", L[idx], "b: ", L[jdx], "c: ", c)
            if ldx == -1: continue
            #print("Input: ", L[:jdx])
            ret += jdx - ldx
            #print("len:", len(L[ldx:jdx]), "L: ", L[ldx: jdx])
    print(ret)

Submission status: Time Limit Exceeded

Solution code:
def lowerBound(nums, target):
    lp = 0
    rp = len(nums) - 1
    mp = lp + rp >> 1
    while lp <= rp:
        mp = lp + rp >> 1
        if nums[mp] == target:
            return mp
        if nums[mp] < target:
            lp = mp + 1
        else:
            rp = mp - 1
    return mp if target < nums[mp] else -1

if __name__ == '__main__':
    N = int(input())
    L = [int(l) for l in input().split()]
    L.sort()
    ret = 0
    for idx in range(len(L) - 1, 1, -1):
        for jdx in range(idx - 1, 0, -1):
            c = L[idx] - L[jdx] + 1
            ldx = lowerBound(L[:jdx], c)
            if ldx == -1: continue
            ret += jdx - ldx
    print(ret)

Submission status: Time Limit Exceeded

Solution code:
def lowerBound(nums, target):
    lp = 0
    rp = len(nums) - 1
    mp = lp + rp >> 1
    while lp <= rp:
        mp = lp + rp >> 1
        if nums[mp] == target:
            return mp
        if nums[mp] < target:
            lp = mp + 1
        else:
            rp = mp - 1
    return mp if target < nums[mp] else -1

if __name__ == '__main__':
    N = int(input())
    L = [int(l) for l in input().split()]
    L.sort()
    ret = 0
    for idx in range(len(L) - 1, 1, -1):
        for jdx in range(idx - 1, 0, -1):
            c = L[idx] - L[jdx] + 1
            ldx = lowerBound(L[:jdx], c)
            if ldx == -1: continue
            ret += len(L[ldx: jdx])
    print(ret)

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

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(c_list,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: Time Limit Exceeded

Solution code:
n=int(input()) #7
e=list(map(int,input().split())) #218 786 704 233 645 728 389 の時
d=sorted(e)
c=0
for i in range(n-2): 
    for j in range(i+1,n-1): 
        for l in range(j+1,n): #jのとなりの704-389まですべて選べる
            if (d[l]<d[i]+d[j]):
                c=c+1 
print(c)

Submission status: Time Limit Exceeded

Solution code:
n=int(input()) 
d=list(map(int,input().split()))
c=0
for i in range(n-2): 
    for j in range(i+1,n-1): 
        for l in range(j+1,n): 
            if (d[i]<d[j]+d[l]) and (d[j]<d[i]+d[l]) and (d[l]<d[i]+d[j]):
                c=c+1 
print(c)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

a = tuple(itertools.combinations(lis,3))
b = 0

for i in a:
    if i[0] < i[1] + i[2] and i[1] < i[2] + i[0] and i[2] < i[0] + i[1]:
        b += 1
print(b)

Submission status: Time Limit Exceeded

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

L_sort = tuple(sorted(L))


def test(total):
	for i in range(N-2):
		tempi = L_sort[i]
		for j in range(i+1,N - 1):
							temp_L = L_sort[j + 1:]
							
							temp_L = tuple(k for k in temp_L if k < tempi + L_sort[j])
							total += len(temp_L)

	return total

if __name__ == '__main__':
	print(test(total))

Submission status: Time Limit Exceeded

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


def solve(N: int, L: "List[int]"):
    L = sorted(L)
    counter = 0
    for a, c in itertools.combinations(L, 2):
        ai = bisect.bisect_left(L, a)
        ci = bisect.bisect_left(L, c)
        left = abs(a-c)
        right = a+c
        lefti = bisect.bisect_right(L, left)
        righti = bisect.bisect_left(L, right)
        tmpcounter = righti - lefti
        if lefti <= ai <= righti:
            tmpcounter -= 1
        if lefti <= ci <= righti:
            tmpcounter -= 1
        counter += max(0, tmpcounter)
 
    print(counter//3)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    L = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, L)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    n = int(input())
    list = [int(i) for i in input().split()]
    list.sort(reverse=True)
    ans = 0
    for i in range(n-2):
        li = list[i]
        if i > n-1:
            break
        for j in range(i,n-1):
            lj=list[j]
            if j>i:
                if j > n:
                    break
                for k in range(j,n):
                    lk = list[k]
                    if k > j:
                        if li < lj+ lk:
                            ans = ans +1
                        else:
                            break
    print(ans)

Submission status: Time Limit Exceeded

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_l = Ln[N-b-1]
            c_threshold = a_l - b_l
            c_list = Ln[0:N-b-1]
            c_idx = bisect.bisect_right(c_list,c_threshold)
            #c_idx = binary_area_search(c_list,c_threshold)
            if c_idx is not None:
                count += len(c_list) - 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: Time Limit Exceeded

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_l = Ln[N-b-1]
            c_threshold = a_l - b_l
            c_list = Ln[0:N-b-1]
            #c_idx = bisect.bisect_right(c_list,c_threshold)
            c_idx = binary_area_search(c_list,c_threshold)
            if c_idx is not None:
                count += len(c_list) - 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: Time Limit Exceeded

Solution code:
n=int(input())
L=sorted(list(map(int,input().split())),reverse=True)
L1 = []
cnt=0
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if L[i] < L[j] + L[k]:
                cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

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

a.sort()
count = 0


def binary_search(numbers, target_number):
    # 最小値を仮決め
    low = 0
    # 範囲内の最大値
    high = len(numbers)


    # 目的地を探し出すまでループ
    while low <= high:
        if low == high:
            return low
        # 中央値を求める（index）
        middle = (low + high) // 2
        # 中央値のnumbersの値とtarget_numberが等しい場合
        if numbers[middle] == target_number:
            return middle
        # 中央値のnumbersの値がtarget_numberより小さい場合
        elif numbers[middle] < target_number:
            low = middle + 1
        # 中央値のnumbersの値がtarget_numberより大きい場合
        else:
            high = middle - 1
    return max(low, high)


for i in range(n-2):
    for j in range(i+1, n-1):
        if a[i] + a[j] > max(a):
            count += n - (j+1)
            continue
        elif a[i] + a[j] == max(a):
            count += n - (j+1) - 1
            continue
        index = binary_search(a, (a[i]+a[j]))
        if a[i] + a[j] == a[index] or a[i] + a[j] < a[index]:
            count += (index-(j+1))
        else:
            count += (index - j)


print(count)

Submission status: Time Limit Exceeded

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

count = 0

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 binary_area_search(target_list: list, target_item: int) -> int:
    '''
    @params
    target_list: [5,3,1](DESC)
    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 == high:
                return None
            if target_list[mid+1] > target_item:
                return mid + 1 
            low = mid + 1
    return None



for a in range(N):
    a_l = Ln[a]
    '''
    N^2*logN
    '''
    for b in range(a+1, N):
        b_l = Ln[b]
        c_threshold = a_l - b_l
        c_list = Ln[b+1:N]
        c_list.reverse()
        c_idx = bisect.bisect_right(c_list,c_threshold)
        #c_idx = binary_area_search(c_list,c_threshold)
        if c_idx is not None:
            count += len(c_list) - c_idx
    '''
    N^2
    '''
    '''
    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)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())

str_list = input().split(' ')
int_list = [int(x) for x in str_list]

count = 0
for ii in range( len(int_list) ):
    for jj in range( ii+1, len(int_list) ):
        for kk in range( jj+1, len(int_list) ):
            if int_list[ii]<int_list[jj]+int_list[kk] and int_list[jj]<int_list[ii]+int_list[kk] and int_list[kk] < int_list[ii]+int_list[jj]:
                count += 1
print(count)

Submission status: Time Limit Exceeded

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

count = 0

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

for a in range(N):
    a_l = Ln[a]
    '''
    N^2*logN
    '''
    for b in range(a+1, N):
        b_l = Ln[b]
        c_threshold = a_l - b_l
        c_list = Ln[b+1:N]
        c_list.reverse()
        c_idx = binary_area_search(c_list,c_threshold)
        if c_idx is not None:
            count += len(c_list) - c_idx
    '''
    N^2
    '''
    '''
    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)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
n=int(input())
l=list(map(int, input().split()))
combl=list(combinations(l,3))
combl.append(0)
count=0
i=0
while combl[i]!=0:
	if combl[i][0]<combl[i][1]+combl[i][2] and combl[i][1]<combl[i][2]+combl[i][0] and combl[i][2]<combl[i][0]+combl[i][1]:
		count+=1
	i+=1
print(count)