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:
import sys
input = sys.stdin.readline
N =int(input())
L = list(map(int,input().split()))
L.sort()

def se(x,s,e,L,n):
	t = (e+s+1)//2
	if x <= L[s]:
		return(0)
	elif s==e:
		return(int(s-n+1))
	elif x >L[t]:
		return(se(x,t,e,L,n))
	elif x <=L[t]:
		return(se(x,s,t-1,L,n))

c = 0
for i in range(0,N-2):
	for j in range(i+1,N-1):
		x = L[i] + L[j]
		c += se(x,j+1,N-1,L,j+1)
print(c)

Submission status: Time Limit Exceeded

Solution code:
import bisect

N=[int(x)for x in input().split()]
D=[int(x) for x in input().split()]

D.sort()
total=0

for i in range(len(D)-2):
    for j in range(i+1,len(D)-1):
        total+= bisect.bisect_left(D[j+1:],D[i]+D[j])

print(total)

Submission status: Time Limit Exceeded

Solution code:
import bisect

N=[int(x)for x in input().split()]
D=[int(x) for x in input().split()]

D.sort()
total=0

for i in range(len(D)-2):
    for j in range(i+1,len(D)-1):
        v=D[i]-D[j]
        total+= bisect.bisect_left(D[j+1:],D[i]+D[j])


print(total)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=[0]*1010
for i in list(map(int,input().split())):x[i]+=1
ans=0
for a in range(1,1001):
  for b in range(a,1001):
    for c in range(b,1001):
      if a<b+c and b<c+a and c<a+b:
        if a==b==c:ans+=x[a]*(x[b]-1)*(x[c]-2)//6
        elif a==b:ans+=x[a]*(x[b]-1)*x[c]//2
        elif b==c:ans+=x[a]*x[b]*(x[c]-1)//2
        else:ans+=x[a]*x[b]*x[c]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n=int(input())
cnt=0
l= list(map(int, input().split()))
l.sort(reverse=True)
k=[[0 for i in range(n-2)] for j in range(n-2)]
for i in range(n-2):
    for j in range(i,n-2):
        k[i][j-i]=-l[i+1]-l[j+2]
#print(k)
for i in range(n-1):
    x=i
    while x<n-2:
        cnt+=bisect.bisect_left(k[x],-l[i])
        #print(l[i],bisect.bisect_left(k[x],-l[i]))
        x+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N = int(input())

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

edge = list(itertools.combinations(L,3))

con = 0

for i in range(0,len(edge)):
	edge[i] = list(edge[i])
	edge[i].sort(reverse = True)
	a = edge[i][0]
	b = edge[i][1]
	c = edge[i][2]
	if a < b + c:
		con += 1
		
print(con)

Submission status: Time Limit Exceeded

Solution code:
n= int(input())
l = list(map(int,input().split()))
ans = 0
L = sorted(l, reverse=True)

for i in range(n-2):
    for j in range(i+1, n-1):
        ans += len([x for x in L[j+1:] if x + L[j] > L[i]])
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# D - Triangles
n = (int)(input())
length = list(map(int, input().split()))

sum = 0

for i in range(n):
    for j in range(n):
        for k in range(n):

            a = length[i]
            b = length[j]
            c = length[k]


            if i >= j or i >= k or j >= k:
                continue

            if a < b + c and b < c + a and c < a + b:
                sum += 1

print(sum)

Submission status: Time Limit Exceeded

Solution code:
import bisect

N = int(input())
L = input().split()
for i in range(0, N):
  L[i] = int(L[i])
L.sort()
ans = 0
for i in range(0, N-1):
  for j in range(i+1, N):
    a = L[j] - L[i]
    b = L[j] + L[i]
    c = bisect.bisect_right(L, a)
    d = bisect.bisect_left(L, b)
    if 2*L[i] > L[j]:
      ans += d-c-2
    else:
      ans += d-c-1
print(ans // 3)

Submission status: Time Limit Exceeded

Solution code:
N, *L = map(int, open(0).read().split())
#print(N, L)
sides = []
for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            sides.append([L[i],L[j],L[k]])
#print(sides)
cnt = 0
for side in sides:
    if (side[0]<side[1]+side[2]) and (side[1]<side[0]+side[2]) and (side[2]<side[0]+side[1]):
        cnt += 1
        #print(side[0],side[1],side[2])
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import copy

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

cout = 0
m,k = 0,0

for i in range(n-2):
	o = list1.pop(0)
	list1_c = copy.deepcopy(list1) #ここでjのためのdeepcopyを更新
	for j in range(n-i-1):
		p = list1_c.pop(0)

		a = abs(o-p) +1
		b = o+p -1 #<= ではなく<条件に揃える

		d = bisect.bisect_right(list1_c,b)
		
		cout += d

print(cout)

Submission status: Time Limit Exceeded

Solution code:
def triangles(a): 
    n = len(a) 
    a.sort() 
    count = 0
    for i in range(0,n-2):
        for j in range(i+1,n): 
            k=j+1
            while (k < n and a[i] + a[j] > a[k]): 
                k += 1
            if(k>j): 
                count += k - j - 1
    return count
n=int(input())
a=list(map(int,input().split()))
print(triangles(a))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import sys
from collections import defaultdict

input = sys.stdin.readline


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

        ans = 0

        for a,b,c in itertools.combinations(L,3):
            if a < b + c and b < c + a and c < a + b:
                ans += 1

        print(ans)


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
N=int(input())
ll=list(map(int,input().split()))
ll.sort()
ans=0
for i in range(N):
    for j in range(i+1,N):
        delta=bisect_left(ll,ll[i]+ll[j],lo=j)-j-1
        if delta>0:
            ans+=delta
        #print(i,j,delta)
print(ans)

Submission status: Time Limit Exceeded

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
L=list(map(int,input().split()))
L.sort(reverse=True)
t=0
for i in range(N):
    for j in range(i+1,N):
        if 2*L[j]<L[i]:
            break
        for k in range(j+1,N):
            if L[i]<L[j]+L[k]:
                t+=1
            else:
                break

print(t)

Submission status: Time Limit Exceeded

Solution code:
def search(L, n, base=0):
    if len(L) == 1:
        if L[0] > n:
            return base - 0.5
        elif L[0] == n:
            return base
        else:
            return base + 0.5
    ind = len(L) // 2
    if L[ind] > n:
        return search(L[:ind], n, base)
    elif L[ind] == n:
        return base + ind
    else:
        return search(L[ind:], n, base+ind)

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):
        a = L[i]
        b = L[j]
        min_c = abs(a - b) + 1
        max_c = a + b - 1

        min_ind = search(L, min_c)
        if isinstance(min_ind, float):
            min_ind = int(min_ind + 1)
        min_ind = max(min_ind, j + 1)
        max_ind = int(search(L, max_c))

        ans += max_ind - min_ind + 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

tri = list(itertools.combinations(L, 3))
ans = 0

for t in tri:
  if t[0]<t[1]+t[2] and t[1]<t[0]+t[2] and t[2]<t[0]+t[1]:
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

import itertools
C = list(itertools.combinations(L,3))
l = len(C)

for i in range(l):
    s = sorted(C[i])
    if s[0] + s[1] <= s[2]:
        pass
    else:
        count = count + 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

Lsorted = sorted(L)
ret = 0
cnt = 0
for i in range(N):
  for j in range(i+1,N):
    a = Lsorted[i]
    b = Lsorted[j]
    x = a + b
    max_idx = bisect.bisect_left(Lsorted, x)
    for k in range(j+1, max_idx):
      c = Lsorted[k]
      
      cnt += 1
      if c >= (a + b):
        break
      if b >= (a + c):
        break
      if a >= (b + c):
        break
      
      ret += 1
print(ret)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right

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

ans = 0
for i, A in enumerate(L):
    for j, B in enumerate(L):
        if i == j:
            continue
        left = bisect_right(L, abs(A - B))
        right = bisect_left(L, A + B)

        ans += right - left

        if left <= i < right:
            ans -= 1
        if left <= j < right:
            ans -= 1

print(ans // 6)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
L=[int(i) for i in input().split()]
L.sort()
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[k]<(L[i]+L[j]):
        cnt+=1
      else:
        break
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np
N = int(input())
L = np.array(sorted(list(map(int, input().split()))))

count = N * (N - 1) * (N - 2) // 6
error = 0
for i in range(N):
  for j in range(i):
    a = L[i]
    b = L[j]
    error += (L >= (a + b)).sum()
print(count  - error)

Submission status: Time Limit Exceeded

Solution code:
def Triangles(N, Lrand):
    asc = sorted(Lrand)
    desc = sorted(Lrand, reverse=True)
    cnt = 0
    for i in range(N-2):
        if desc[i] >= desc[i+1]*2: break
        for j in range(i+1, N-1):
            if desc[i] >= desc[j] + desc[i+1]: break
            for k in range(N-j-1):
                if desc[i] - desc[j] < asc[k]:
                    cnt += N-j-k-1
                    break
    return cnt

N = int(input())
L = [int(x) for x in input().split()]
print(Triangles(N, L))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=[0]*n
l[:]=map(int,input().split())
ans=0
m=10**3
l=sorted(l)[::-1]
for i in range(n-2):
  m=min(m,l[i])
  for j in range(i+1,n-1):
    for k in range(j+1,n):
      if m<l[j]+l[k]:
        ans+=1
      else:
        break
print(ans)

Submission status: Time Limit Exceeded

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


ans = 0
for i in range(N - 1 , 1, -1):
    for j in range(i - 1 , 0 , -1):
        work = l[:j]
        x = l[i] - l[j]
        idx = bisect.bisect_right(work, x)
        ans += len(work) - idx
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
L=[int(i) for i in input().split()]
L.sort()
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[k]<(L[i]+L[j]):
        cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
L = input().split()
total = 0
for i in range(N):
	L[i] = int(L[i])
	
for i in range(N):
	for j in range(i,N):
		if not i == j:
			for k in range(j,N):
				if not ((j == k)):
					if not (i == k):
						if L[k]<L[i]+L[j] and L[i]<L[k]+L[j]:
							if L[j]<L[i]+L[k]:
				  				total += 1
print(total)

Submission status: Time Limit Exceeded

Solution code:
import sys
N=int(input())
d=sorted(list(map(int,input().split())))
ans=0
while len(d)>=3:
  c=d.pop(-1)
  tmp=[]
  for i in range(len(d)-1):
    for j in range(i+1,len(d)):
      if d[i]+d[j]>c:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
L=list(map(int,input().split()))
L.append(0)
L.sort(reverse=True)
t=0
for i in range(N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            if L[i]<L[j]+L[k]:
                t+=1
            else:
                break

print(t)

Submission status: Time Limit Exceeded

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)
p_list = []

for a_i, a in enumerate(l_list):
    for b_i, b in enumerate(l_list):
        if a_i == b_i:
            continue

        c_kouho = a + b
        c_i = bisect.bisect_left(l_list, c_kouho)
        p_list += [
            sorted([a, b, c])
            for c_i, c in enumerate(l_list[: c_i + 1])
            if c_i != a_i and c_i != b_i and abs(b - c) < a < b + c
        ]

p_list = ["{}_{}_{}".format(p[0], p[1], p[2]) for p in p_list]
ans = len(set(p_list))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
L = list(map(int,input().split()))
cnt = 0
L.sort()
for i in range(N):
    for j in range(i+1,N):
        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:
import bisect
import copy

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

cout = 0
m,k = 0,0

for i in range(n-2):
	o = list1.pop(0)
	list1_c = copy.deepcopy(list1) #ここでjのためのdeepcopyを更新
	for j in range(len(list1)):
		p = list1_c.pop(0)

		a = abs(o-p) +1
		b = o+p -1 #<= ではなく<条件に揃える

		#c = bisect.bisect_left(list1_c,a)
		d = bisect.bisect_right(list1_c,b)

		if d>=1:
			cout += d

print(cout)

Submission status: Time Limit Exceeded

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

L.sort()
tss=[]
for i in range(N-2):
    for j in range(1,N-i):
        tss.append(L[i]+L[i+j])

num=[]
for i in range(1,N-1):
    for j in range(i,N):
        num.append(j)
        
ans=0
for i in range(len(tss)):
    for j in range(num[i]+1,N):
        if tss[i]>L[j]:
            ans+=1
        else:
            break
    else:
        continue
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#from collections import Counter

#import numpy as np

#input = raw_input
n = int(input())
#nums = np.zeros(2001, dtype=int)
nums = [0] * 2001
#nums = np.zeros(2001, dtype=int)

ls = map(int, input().split(" "))
#ls = Counter(map(int, ls))
#vals = ls.keys()
ls = sorted(ls)
for l in ls:
    #print(l)
    nums[l] += 1

set_vals = [val for val in range(2001) if nums[val] >= 1]
#print(vals)

#cumsum = np.cumsum(nums)

#print(set_vals)
len_set = len(set_vals)
out = 0
for i in range(len_set):
    val1 = set_vals[i]
    num_i = nums[val1]
    if num_i >= 3:
        out += (num_i * (num_i-1) * (num_i-2) // 6)
    
    if num_i >= 2:
        val2 = set_vals[i]
        for j in range(i+1, len_set):
            val3 = set_vals[j]
            num_h = nums[val3]
            if 2 * val1 <= val3:
                break

            out += ((num_i * (num_i-1)) // 2) * num_h

    for j in range(i+1, len_set):
        val2 = set_vals[j]
        num_j = nums[val2]

        if num_j >= 2:
            out += (num_i *  num_j * (num_j - 1) // 2 )

        for h in range(j+1, len_set):
            val3 = set_vals[h]
            #print(val1, val2, val3)
            num_h = nums[val3]
            if val1 + val2 <= val3:
                break

            #print("num", num_i, num_j, num_h)
            out += (num_i * num_j * num_h)

print(out)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

su=0
t=1
for i in range(n-1):
    if L[i]==L[i+1]:
        t+=1
    else:
        su+=t*(t-1)*(t-2)//6
        t=1
su+=t*(t-1)*(t-2)//6

t=1
for i in range(n-1):
    if L[i]==L[i+1]:
        t+=1
    else:
        su+=(bisect.bisect_left(L, 2*L[i])-t)*t*(t-1)//2
        t=1
su+=(bisect.bisect_left(L, 2*L[i])-t)*t*(t-1)//2

for i in range(n):
    for j in range(n):
        if i<j:
            su+=max(0,bisect.bisect_left(L,L[i]+L[j])-max(bisect.bisect_right(L,L[i]),bisect.bisect_right(L,L[j])))

print(su)

Submission status: Time Limit Exceeded

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

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

lines.sort()
# print(lines)

sum = 0
for i in range(N):
    for j in range(i + 2, N):
        # print("i,j:{0},{1}".format(i, j))
        # print("lines[i],lines[j]:{0},{1}".format(lines[i], lines[j]))
        k = j - 1
        while i < k:
            # print("i,j,k:{0},{1},{2}".format(i, j, k))
            # print("lines[i],lines[j],lines[k]:{0},{1},{2}".format(lines[i], lines[j], lines[k]))

            if ((lines[i] + lines[j]) > lines[k]) and (lines[i] + lines[k]) > lines[j]:
                # print("count up")
                sum += 1
            if (lines[i] + lines[k] <= lines[j] or lines[j] + lines[k] <= lines[i]):
                break
            k -= 1
print(sum)

Submission status: Time Limit Exceeded

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):
    small = L[i]

    for j in reversed(range(i+2, N)):
      large = L[j]
      target = large - small + 1
      pos = bisect.bisect_left(L[:j], target)
      # print(i, j, pos)
      #if(i <= pos):
      ans += j- max(i+1, pos)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def calc(N, L):
    L.sort()
    r = 0
    for i in range(N - 2):
        for j in range(i + 1, N - 1):
            lij = L[i] + L[j]
            left = j + 1
            right = N - 1
            k = (left + right) // 2
            while True:
                if L[k] >= lij:
                    right = k
                else:
                    left = k
                _k = (left + right) // 2
                if _k == k:
                    break
                else:
                    k = _k
            r += right - j - 1 + (1 if lij > L[right] else 0)
    return r


N = int(input())
L = [int(s) for s in input().split()]
print(calc(N, L))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
L = list(map(int, input().split()))
L.sort()
count = 0
max_val = 0

for i in range(0, N-2):
	for j in range(i+1, N-1):
		for k in range(j+1, N):
			if (L[k] < (L[i]+L[j])):
				count += 1
			else:
				break

print(count)

Submission status: Time Limit Exceeded

Solution code:
import heapq

N = int(input())
L_list = list(map(int,input().split()))
L_list.sort()
ans = 0
list = []
M = 0

for i in range(N-1):
    for j in range(N-i-1):
        list.append((L_list[i]+L_list[j+i+1],i,j+i+1))
        M += 1

for k in range(N):
    for z in range(M):
        if L_list[k] < list[z][0]:
            if (k > list[z][2]):
                ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

ans = 0

for i in range(N-2):
  for j in range(i+1,N-1):
    for k in range(j+1,N):
      li = L[i]
      lj = L[j]
      lk = L[k]
      if ((li+lj)>lk)&((lj+lk)>li)&((li+lk)>lj):
        ans += 1
      else:
        continue
        
print(ans)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

def se(x,s,e,L,n):
	t = (e+s+1)//2
	#print(x,s,t,e,L,n)
	if x <= L[s]:
		return(0)
	elif s==e:
		#print(int(s-n+1))
		return(int(s-n+1))
	elif x >L[t]:
		return(se(x,t,e,L,n))
	elif x <=L[t]:
		return(se(x,s,t-1,L,n))

c = 0
for i in range(0,N-2):
	for j in range(i+1,N-1):
		x = L[i] + L[j]
		#print(x,j+1,N-1,se(x,j+1,N-1,L,j+1))
		c += se(x,j+1,N-1,L,j+1)
print(c)

Submission status: Time Limit Exceeded

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

cnt = 0
for a in range(n):
  for b in range(a+1,n):
    for c in range(b+1,n):
      if L[a] >= L[b] + L[c]:
        continue
      elif L[b] >= L[a]+L[c]:
        continue
      elif L[c] >= L[a] + L[b]:
        continue
      else:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import bisect

N=[int(x)for x in input().split()]
D=[int(x) for x in input().split()]

D.sort(reverse=True)
total=0
# print(D)
def check(a,b,c): #3
    if(a<b+c):
        if(b<a+c):
            if(c<a+b):
                return True
    return False

for i in range(len(D)-1):
    for j in range(i+1,len(D)-1):
        #print("i="+str(i)+" j="+str(j))
        v=D[i]-D[j]
        # print(D[:j:-1])
        # print("v="+str(v))
        # print(len(D[:j:-1]) -bisect.bisect_left(D[:j:-1],v))
        total+=len(D[:j:-1]) - bisect.bisect_left(D[:j:-1],v+0.1)


        # for k in range(j + 1, len(D)):
        #     if(check(D[i],D[j],D[k])):
        #         total+=1
        #         print(str(i)+" "+str(j)+" "+str(k)+"   "+str(total))


print(total)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=sorted(list(map(int, input().split())))
ans=0
count=0
for i in range(n-2):  
  l,r=i+1,i+2
  sums=s[i]+s[l]
  while r<n:
    if s[r]<sums:
      count+=1
      if r==n-1:
        ans+=count
        count=0
        sums=sums-s[l]+s[l+1]
        l+=1
        r=l
      r+=1
    elif l==r:
      r+=1
    else:
      ans+=count
      count=0
      sums=sums-s[l]+s[l+1]
      l+=1
      r=l+1
print(ans)

Submission status: Time Limit Exceeded

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

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

lines.sort()
# print(lines)

sum = 0
for i in range(N):
    for j in range(i + 2, N):
        # print("i,j:{0},{1}".format(i, j))
        # print("lines[i],lines[j]:{0},{1}".format(lines[i], lines[j]))
        k = j - 1
        while i < k:
            # print("i,j,k:{0},{1},{2}".format(i, j, k))
            # print("lines[i],lines[j],lines[k]:{0},{1},{2}".format(lines[i], lines[j], lines[k]))

            if ((lines[i] + lines[j]) > lines[k]) and (lines[i] + lines[k]) > lines[j]:
                # print("count up")
                sum += 1
            if (lines[i] + lines[k] <= lines[j]):
                break
            k -= 1
print(sum)

Submission status: Time Limit Exceeded

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

L = sorted(L)

count = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        ab_num = [i, j]
        for k in range(j+1, N):
            if k not in ab_num:
                if L[ab_num[0]] + L[ab_num[1]] > L[k]:
                    count += 1
                else:
                    break


print(count)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right

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

L.sort()

cnt = 0
for i in range(1, N - 1):
    b = L[i]
    for j in range(i):
        a = L[j]
        l, r = bisect_left(L, b - a + 1, lo=i), bisect_right(L, a + b - 1, lo=i)
        cnt += r - l - (l <= i <= r) - (l <= j <= r)

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

ans = 0

for i in range(n):
	d = []
	for j in range(i+1,n):
		index = bisect.bisect_left(l,l[i]+l[j])
		for k in range(i+1,j):
			if l[j] < l[k] + l[i]:
				if [k,j] not in d:
					d.append([k,j])
					ans += 1
		for k in range(j+1,index):
			if l[k] < l[j] + l[i]:
				if [j,k] not in d:
					d.append([j,k])
					ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = [int(_) for _ in input().split()]
ans = 0
L = [0 for _ in range(1,4000+1)]
s = [0 for _ in range(0,4000+1)]
for k in range(0, n):
    L[l[k]-1] += 1
for x in range(0,4000):
    s[x+1] = s[x] + L[x]

for i in range(0, n-1):
    for j in range(i+1, n):
        exc = 0
        m = abs(l[i] - l[j])
        M = l[i] + l[j]
        if l[i] > m:
            exc += 1
        if l[j] > m:
            exc += 1
        ans += s[M] - s[m] - L[M-1] - exc
print(ans//3)

Submission status: Time Limit Exceeded

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

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

count = 0

for combi in itertools.combinations(l_list, 3):
    a = combi[0]
    b = combi[1]
    c = combi[2]
    if a<b+c and b<c+a and c<a+b:
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
L=list(map(int,input().split()))
c=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] and L[j]<L[i]+L[k] and L[k]<L[i]+L[j]:
        c=c+1
print(c)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N = int(input())
L = list(map(int, input().split()))
C = list(itertools.combinations(L, 3))

count = 0

for i in C:
    if i[0] < i[1] + i[2] and i[1] < i[0] + i[2] and i[2] < i[0] + i[1]:
        count += 1

print(count)

Submission status: Time Limit Exceeded

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

# 昇順にする
L.sort()

count=0
for i in range(N):
    for j in range(i+1,N):
        for n in range(j+1,N):
            if L[n]<L[i]+L[j]:
                count+=1
            else:
                break
print(count)

Submission status: Time Limit Exceeded

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

num=0
for i in range(N-2):
  for j in range(N-2-i):
    if (wood[i] > wood[N-1] - wood[N-2]):
      for k in range(N-2-i-j):
        if ((wood[i] < wood[j+i+1] + wood[k+1+i+j+1]) and (wood[j+1+i] < wood[i] + wood[i+j+2+k]) and ((wood[k+i+j+2] < wood[i] + wood[j+1+i]))):
          num += 1
        
      
        
      
    
print(num)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
''' 
------------------------
author : iiou16
------------------------
'''
import copy
import numpy as np
def main():
    N = int(input())
    L = list(map(int, input().split()))

    count = 0
    L = np.array(L)
    for i in range(N):
        a = L[i]
        for j in range(i+1, N-1):
            b = L[j]
            _L = L[j+1:]
            C = _L[(_L < a + b)]
            res = C[C > abs(a - b)]
            count += len(res)
    print(count)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
L=list(map(int, input().split()))
L.sort()
L.reverse()
a=L.pop(0)
count=0
while(L!=[]):
    for i in range(len(L)):
        for j in range(i+1,len(L)):
            if a < L[i]+L[j]:
                count+=1
    a=L.pop(0)
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
 
n = int(input())
h = list(map(int, input().split()))
def triangle(n,h):
    x = 0
    for i in range(n-2):
        for j in range(i+1,n-1):
            for k in range(j+1, n):
                if h[i] < h[j] + h[k] and h[j] < h[i] + h[k] and h[k] < h[j] + h[i]:
                    x = x + 1
    return x
print(triangle(n,h))

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

N=int(input())
L=input()
L=L.split()
L=[int(item) for item in L]
L.sort()
ans=cmb(N,3)
for i in range(N-2):
    for j in range(i+1,N-1):
        for k in reversed(range(j+1,N)):
            if (L[i]+L[j])>L[k]:
                break
            else:
                ans-=1


print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())
l = sorted([int(x) for x in input().split()])
#print(l)
np_l = np.array(l)
ans = 0

for a in range(n):
    for b in range(a+1, n):
        ll = l[b+1:]
        np_ll = np.array(ll)
        np_ll = np_ll[np_ll < (np_l[a]+np_l[b])]
        #print(l[a], l[b], np_ll)
        ans += len(np_ll)
        """for c in range(b+1, n):
            if l[c]<l[a]+l[b]:
                ans += 1
                print(a,b,c)
                continue
            else:
                break"""
print(ans)

Submission status: Time Limit Exceeded

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


def solve(N: int, L: "List[int]"):
    L.sort()
    ans = 0
    for i, l in enumerate(L[2:]):
        way2 = sorted([sum(x) for x in itertools.combinations(L[: 2 + i], 2)])
        ans += len(way2) - bisect.bisect_right(way2, l)
    print(ans)
    return


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:
import itertools

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

def tri_d(a,b,c):
  if (a+b>c) and (b+c>a) and (c+a>b):
    return True
  else:
    return False


ans=0
C=list(itertools.combinations(L, 3))
for a,b,c in C:
  if tri_d(a,b,c):
    ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N=int(input())
L=list(map(int,input().split()))
ans=0
for x in itertools.combinations(L,3):
  if x[0]<x[1]+x[2] and x[1]<x[0]+x[2] and x[2]<x[0]+x[1]:
    ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

# all_sample = N * (N-1) * (N-2) / 6

a = list(itertools.combinations(L, 3))

ans = 0

for i in a:
    s = sum(i)
    if i[0] < s/2 and i[1] < s/2 and i[2] < s/2:
        ans += 1

print(ans)