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: Runtime Error

Solution code:
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: Runtime Error

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

Submission status: Runtime Error

Solution code:
n = int(input())
ln = sorted([int(i) for i in input().split()])
ans = 0
for j in range(n - 2):
    for k in range(j+1,n - 1):
        if j >= k:
            continue
        else:
            if ln[j] + ln[k] > ln[k + 1]:
                ans += len(ln[k+1])
                for l in range(k + 1, n):
                    if ln[j] + ln[k] > ln[l]:
                        if ln[j] + ln[l] > ln[k]:
                            if ln[l] + ln[k] > ln[j]:
                                ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
L=list(map(int,input().split()))
d=[]
s=0
def triagles(a,b,c):
    if a<b+c and b<a+c and c<a+b:
        d+=set([a,b,c])
        return 1
    else:
        return 0
for i in range(N):
    for j in range(N):
        for k in range(N):
            if i!=j and j!=k and k!=i:
                if set([L[i],L[j],L[k]]) not in d:
                    s+=triagles(L[i],L[j],L[k])
print(s)

Submission status: Runtime Error

Solution code:
# D TLE
import bisect

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

L.sort()
value = 0


for i in range(0, len(L)-2):
    for j in range(i, len(L)-1):
    index = bisect.bisect_left(L[j+1:], L[i]+L[j])
    value+=max(0, index)

print(value)

Submission status: Runtime Error

Solution code:
n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
#a[b]の答え
at = []
def at_memo(x):
    if x==0:
        return []
    if x in at:
        return at[x]
    atx = [l[x]+l[i] for i in range(x)]  
    at[x] = at[x-1] + atx
    return at[x]

for x in range(1,n):
    for i in range(len(at_memo(x-1))):
        if l[x]-at_memo(x-1)[i]>0:
            ans += 1
        else:
            continue

Submission status: Runtime Error

Solution code:
# D TLE
import bisect

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

L.sort()
value = 0


for i in range(0, len(L)-2)
    for j in range(i, len(L)-1)
    index = bisect.bisect_left(L[j+1:], L[i]+L[j])
    value+=index

print(value)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 8)

from itertools import accumulate


fact = [1]

for i in range(1, 1001):
    fact.append(fact[-1] * i)


def comb(n, r):
    return fact[n] / fact[r] / fact[n-r]


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

    nums = [0] * 1001

    for e in l:
        nums[e] += 1

    acm = list(accumulate(nums))

    l.sort()
    ans = 0
    tmp = [0] * 1001
    tmp2 = [[0] * 1001 for _ in range(1001)]
    for i in range(n-2):
        for j in range(i+1, n-1):
            a = l[i]
            b = l[j]
            k = min(1000, a+b-1)

            # b < c のときの数
            cnt = acm[k] - acm[b]

            # b == c のときの補正
            if nums[b] >= 3 and a == b and tmp[b] == 0:
                cnt += int(comb(nums[b], 3))
                tmp[b] = 1

            if nums[b] >= 2 and a != b and tmp2[a][b] == 0:
                cnt += int(comb(nums[b], 2)) * nums[a]
                tmp2[a][b] = 1

            ans += cnt

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
from itertools import combinations
import bisect
import math
n = int(input())
l_ls = [int(i) for i in sys.stdin.readline().split()]
l_ls.sort()
#l_dict = { i : j for i, j in enumerate(l_ls)}
_sum_ls = []
cnt = 0
for combi in combinations(l_ls, 2):
    _sum = combi[0] + combi[1]
    ind = bisect.bisect_left(l_ls, _sum)
    cnt += n - ind
print(int(math.factorial(n) / math.factorial(3) / math.factorial(n-3)) - cnt)

Submission status: Runtime Error

Solution code:
import bisect
from collections import Counter
N = int(input())
l = map(int,input().split())
l = sorted(l)
l_dict = dict()
max_l  = max(l)
min_l = min(l)
t_list = [one for one in l if one+min_l < max_l]
for i,one in enumerate(t_list):
    l_dict[one] = i
    
    
big_dict = dict()
for one in t_list:
    big_dict[one] = bisect.bisect_left(l,2*one)

counter = 0

for a,b in combinations(t_list,2):
    tmp = a + b
    counter += bisect.bisect_left(l[l_dict[b]+1:big_dict[b]],tmp)

print(counter)

Submission status: Runtime Error

Solution code:
import bisect
from collections import Counter
N = int(input())
l = map(int,input().split())
l = sorted(l)
l_dict = dict()
max_l  = max(l)
min_l = min(l)
t_list = [one for one in l if one+min_l < max_l]
for i,one in enumerate(t_list):
    l_dict[one] = i
    
    
big_dict = dict()
for one in t_list:
    big_dict[one] = bisect.bisect_left(l,2*one)

counter = 0

for a,b in combinations(t_list,2):
    tmp = a + b
    counter += bisect.bisect_left(l[l_dict[b]+1:big_dict[b]],tmp)

Submission status: Runtime Error

Solution code:
import heapq

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

heapq.heapify(l)
count = 0
for i in range(n-2):
    x = i
    while l[i*-1-1] < l[x*-1-2] + l[x*-1-3]:
        count += 1
        x -= 1
        if x*-1-3 < -n:
            break
print((n-2)*(n-3)/2-count)

Submission status: Runtime Error

Solution code:
N = int(input())
l = map(int,input().split())
l = sorted(l)
l_dict = dict()
max_l  = max(l)
min_l = min(l)
t_list = [one for one in l if one+min_l < max_l]
for i,one in enumerate(t_list):
    l_dict[one] = i
    
    
big_dict = dict()
for one in t_list:
    big_dict[one] = bisect.bisect_left(l,2*one)

counter = 0

for a,b in combinations(t_list,2):
    tmp = a + b
    counter += bisect.bisect_left(l[l_dict[b]+1:big_dict[b]],tmp)

Submission status: Runtime Error

Solution code:
n=int(input())
arr=list(map(int,input().split()))
arr=sorted(arr)
ans=0
for i in range(n):
  a=arr[i]
  for j in range(i+1,n):
    b=arr[j]
    tmp=a+b
    pos=bisect.bisect_left(arr,tmp)-1
    if pos<=j:
      continue
    else:
      ans+=(pos-j)
print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
b=[]
L=[]
b=input().split()

for i in range(N):
    L.append(int(b[i]))
L.sort()
x=0
index=0
for i in range(N-2):
    x=L[0]
    L.remove(L[0])
    for k in range(N-3):
        if (x + L[k]) > L[k+1]:
            index+=1
print(index)

Submission status: Runtime Error

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-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: Runtime Error

Solution code:
import heapq

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

heapq.heapify(l)
for i in range(n-2):
    x = i
    while l[i*-1-1] < l[x*-1-2] + l[x*-1-3]:
        count += 1
        x -= 1
        if x*-1-3 < -n:
            break
print((n-2)*(n-3)/2-count)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 8)

from itertools import accumulate


def factorial(x):
    if x <= 0:
        return 1

    return factorial(x - 1) * x


fact = [factorial(i) for i in range(1001)]


def comb(n, r):
    return fact[n] / fact[r] / fact[n-r]


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

    nums = [0] * 1001

    for e in l:
        nums[e] += 1

    acm = list(accumulate(nums))

    l.sort()
    ans = 0
    tmp = [0] * 1001
    tmp2 = [[0] * 1001 for _ in range(1001)]
    for i in range(n-2):
        for j in range(i+1, n-1):
            a = l[i]
            b = l[j]
            k = min(1000, a+b-1)

            # b < c のときの数
            cnt = acm[k] - acm[b]

            # b == c のときの補正
            if nums[b] >= 3 and a == b and tmp[b] == 0:
                cnt += int(comb(nums[b], 3))
                tmp[b] = 1

            if nums[b] >= 2 and a != b and tmp2[a][b] == 0:
                cnt += int(comb(nums[b], 2)) * nums[a]
                tmp2[a][b] = 1

            ans += cnt

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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]

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])

un=len(s)
for i in range(un):
    c=s[i]
    if k[c]>=3:
        ans+=k[c]*(k[c]-1)*(k[c]-2)//6
    elif k[c]==2:
        ans+=ak[c]
    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]
        if ak[sc]==0:
            break
        mm=c-sc+1
        if mm<0:
            continue
        elif mm>sc:
            continue # break
        else:
            ans+=k[sc]*(k[sc]-1)//2+ak[sc]-ak[mm]
        #show('ans+=',k[sc]*(k[sc]-1)//2+ak[sc]-ak[mm])
    
print(ans)

Submission status: Runtime Error

Solution code:
import itertools
import heapq
import sys
readline = sys.stdin.readline
# readlines = sys.stdin.readlines
N = int(readline())
#ls = list(map(int, readline().split()))
ls = list(map(lambda x: int(x) * (-1), readline().split()))
#ls *= 100
#N *= 100
heapq.heapify(ls)
ans = 0
# n_comb = N * (N-1) * (N-2) / 6
 
import copy
copy_ls = copy.deepcopy(ls)
for i in range(N):
    max1 = -(heapq.heappop(ls))
    copy_ls1 = copy.deepcopy(ls)
    #print(ls)
    for j in range(N-i-1):
      # print(j, ls)
      max2 = -(heapq.heappop(ls))
      for _ in range(N-i-j-2):
        max3 = -(heapq.heappop(ls))
        if (max1 < max2 + max3):
          #print(max1, max2, max3)
          ans += 1
        else:
          # print('break')
          ls = copy.deepcopy(copy_ls1)
          heapq.heappop(ls)
          copy_ls1 = copy.deepcopy(ls)
          break
      ls = copy.deepcopy(copy_ls1)
      heapq.heappop(ls)
      copy_ls1 = copy.deepcopy(ls)
    
    # print('loop end')    
    ls = copy.deepcopy(copy_ls)

Submission status: Runtime Error

Solution code:
N=int(input())
L=list(map(int,input().split()))
d=[]
s=0
def triagles(a,b,c):
  if a<b+c and b<a+c and c<a+b:
    d+=set([a,b,c])
    return 1
  else:
    return 0
for i in range(N):
  for j in range(N):
    for k in range(N):
      if i!=j and j!=k and k!=i:
        if set([L[i],L[j],L[k]]) not in d:
          s+=triangles(L[i],L[j],L[k])
print(s)

Submission status: Runtime Error

Solution code:
import sys

stdin = sys.stdin

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

def C(n,r):
    if n < 0 or r < 0 or n < r: 
        return 0
    elif n == 0 or r == 0: 
        return 1
    return C(n-1,r-1)+C(n-1,r)

def main():
    n = ni()
    l = sorted(na())
    ans = C(n, 3) // 3
    j = n - 2
    k = n - 1
    dame = []
    for i in range(n - 3, -1, -1):
        if i in dame or j in dame or k in dame:
            continue
        a = l[i]
        b = l[j]
        c = l[k]
        if a < b + c and b < a + c and c < a + b:
            j -= 1
            k -= 1
        else:
            if a > b + c:
                dame.append(i)
            if b > a + c:
                dame.append(j)
            if c > a + b:
                dame.append(k)
    
    for d in dame:
        ans -= C(n - d - 1, 1)

    nn = len(dame)
    if nn >= 3:
        j = n - 2
        k = n - 1
        for i in range(dame - 3, -1, -1):
            a = l[i]
            b = l[j]
            c = l[k]
            if a < b + c and b < a + c and c < a + b:
                ans += 1

    print(ans)

main()

Submission status: Runtime Error

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

l.sort()
#print(l)
cnt=0
for i in range(1000000):
    ll.apend=[0]
for i in range(n):
    ll[l[i]]=1

for i in range(n-2):
    for j in range(i+1,n-1):
        t=l[i]+l[j]
        cnt = cnt+sum(ll[t:n])


        
            


print(cnt)

Submission status: Runtime Error

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

def is_triangle(a, b, c):
  if a < b + c and b < c + a and c < a + b:
    return True
  return False

ans = 0
for i, a in enumerate(ll):
  for j, b in enumerate(ll[i+1:]):
    climit_up = a + b
    climit_down = b - a
    for c in ll[i+j+2:]:
      if c >= (climit_up) or c <= clmit_down:
        break
      if is_triangle(a, b, c):
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
#a[b]の答え
at = []
def at_memo(x):
    if x==0:
        return []
    if x in at:
        return at[x]
    atx = [l[x]+l[i] for i in range(x)]  
    at[x] = at[x-1] + atx
    return at[x]


for i in range(len(at_memo(x-1))):
    if l[x]-at_memo(x)[i]>0:
         ans += 1
    else:
         continue


print(ans)

Submission status: Runtime Error

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):
    delta=bisect_left(ll,ll[i]+ll[i+1],lo=i+1)-i-2
    if delta>0:
        ans+=delta
    in_b=delta+i+1+1
    for j in range(i+2,N):
        if in_b!=N:
            delta=bisect_left(ll,ll[i]+ll[j],lo=in_b)-j-1
        else:
            delta=N
        if delta>0:
            ans+=delta
        in_b=delta+j+1
print(ans)

Submission status: Runtime Error

Solution code:
N = int( input() )
list_t = list( map (int, input().split() )
counter = 0 
a = del list_t[0]
b = del list_t[0:2]
for i in list_t:
	for j in a:
		for k in b:
            if i == (len(list_t) - 3):
              break
            else:
              if i < j + k and j < i + k:
            	if k < i + j:
                	counter += 1
    a = del a[0]
    b = del b[0]

print ( counter )

Submission status: Runtime Error

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

l = sorted(l)
res = {}
count = 0
for i in range(len(l)-1):
    tmp_l = l
    a = l.pop(i)
    b = l.pop(i+1)
    count += len([1 for v in tmp_l if v > b - a and v < a + b])
    

print(count)

Submission status: Runtime Error

Solution code:
N = int(input())
array = list(map(int, input().strip().split()))
array.sort()
item_num=0
triangle_num = 0
for item in array:
	item_num=item_num+1
	for i in range(N,item_num+1,-1):
		for k in range(i-1,item_num,-1):
			if array[i] >= item + array[k]:
				break
			if item < array[i] + array[k] and array[k] < item + array[i]:
				triangle_num = triangle_num + 1
print(triangle_num)

Submission status: Runtime Error

Solution code:
import sys
from itertools import combinations
import bisect
import math
import numpy as np
n = int(input())
l_ls = [int(i) for i in sys.stdin.readline().split()]
l_ls.sort()
l_dict = { i : j for i, j in enumerate(l_ls)}
_sum_ls = []
cnt = 0
count_ls = np.zeros(2*10**3, dtype=np.int64)
for l in l_ls:
    count_ls[:l+1] += 1
for combi in combinations(l_ls, 2):
    ind = count_ls[combi[0] + combi[1]]
    cnt += ind
"""
for combi in combinations(l_ls, 2):
    count_ls[combi[0] + combi[1]:] += 1
    #bisect.insort_left(_sum_ls, combi[0] + combi[1])
len_sum_ls = len(_sum_ls)
for l in l_ls:
    #ind = bisect.bisect_right(_sum_ls, l)
    ind = count_ls[l]
    cnt += ind
"""

print(int(math.factorial(n) / math.factorial(3) / math.factorial(n-3)) - cnt)

Submission status: Runtime Error

Solution code:
N=int(input())
L=list(map(int,input().split()))
count=0
L=sorted(L,reverse=True)
while L[0]>L[1]+L[2]:
  del L[0]
for l in range(N):
  for k in range(l+1,N):
    for j in range(k+1,N):
      inf=abs(L[l]-L[k])
      sup=L[l]+L[k]
      if inf<L[j]<sup:
        count=count+1
print(count)

Submission status: Runtime Error

Solution code:
import sys
from collections import Counter
from bisect import bisect, bisect_left
from fractions import Fraction

def comb(n, k):
    if n < 0 or k < 0:
        pdt = 0
    else:
        pdt = 1
        for s in range(1, k + 1):
            pdt *= Fraction(n - s + 1, s)
    return pdt.numerator

input = sys.stdin.readline
N = int(input())
L = sorted([int(x) for x in input().split()])
c = 0
Lcnt = Counter(L)
Lset = sorted(list(set(L)))
Nset = len(Lset)
for i in range(Nset):
    if Lcnt[Lset[i]] >= 3:
        c += comb(Lcnt[Lset[i]], 3)
        if i == Nset - 1:
            break

    if Lcnt[Lset[i]] >= 2:
        fl = bisect(L, Lset[i])
        fr = bisect_left(L, Lset[i] * 2)
        c += comb(Lcnt[Lset[i]], 2) * (fr - fl)
    for j in range(i + 1, Nset):
        fl = bisect(L, Lset[j])
        fr = min(bisect_left(L, Lset[i] + Lset[j]), len(L) - 1)
        c += Lcnt[Lset[i]] * Lcnt[Lset[j]] * (fr - fl)

if Lcnt[Lset[-1]] >= 2:
    c += Lcnt[Lset[-2]] * comb(Lcnt[Lset[-1]], 2)
print(c)

Submission status: Runtime Error

Solution code:
import itertools

height_num = input()
input_list = input().split()
triangle_list = itertools.combinations(input_list, 3)
triangle_num = 0
for triangle in list(triangle_list):
    triangle = sorted(triangle)
    if triangle[0] + triangle[1] < triangle[2]
        triangle_num += 1
print(triangle_num)

Submission status: Runtime Error

Solution code:
#from collections import Counter

import numpy as np

n = int(input())
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-2) // 6)
    
    if num_i >= 2:
        val2 = set_vals[i]
        for j in range(i+1, len_set):
            val3 = set_vals[j]
            num_j = nums[val3]
            if 2 * val1 <= val3:
                break

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

    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: Runtime Error

Solution code:
import sys

stdin = sys.stdin

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

def C(n,r):
    if n < 0 or r < 0 or n < r: 
        return 0
    elif n == 0 or r == 0: 
        return 1
    return C(n-1,r-1)+C(n-1,r)

def main():
    n = ni()
    l = sorted(na())
    ans = C(n, 3) % 3
    j = n - 2
    k = n - 1
    dame = []
    for i in range(n - 3, -1, -1):
        if i in dame or j in dame or k in dame:
            continue
        a = l[i]
        b = l[j]
        c = l[k]
        if a < b + c and b < a + c and c < a + b:
            j -= 1
            k -= 1
        else:
            if a > b + c:
                dame.append(i)
            if b > a + c:
                dame.append(j)
            if c > a + b:
                dame.append(k)
    
    for d in dame:
        ans -= C(n - d - 1, 1)

    nn = len(dame)
    if nn >= 3:
        j = n - 2
        k = n - 1
        for i in range(dame - 3, -1, -1):
            a = l[i]
            b = l[j]
            c = l[k]
            if a < b + c and b < a + c and c < a + b:
                ans += 1

    print(ans)

main()

Submission status: Runtime Error

Solution code:
N = int(input())
L = sorted(list(map(int,input().split())))
s = 0
if N < 10^3:
    for i in range(0,N-2):
        for k in range(i+1,N-1):
            for t in range(k+1,N):
                if L[t] >= L[i] + L[k]:
                    break
                else:
                    s += 1
elif (1.0*10^3) <= N and (1.4*10^3):
    s = N*(N-1)*(N-2)//6
    for i in range(N-400,400,-1):
        for k in range(399,i-1):
            for t in range(k+1,i):
                if L[i] < L[k] + L[t]:
                    break
                else:
                    s -= 1

else:
    s = N*(N-1)*(N-2)//6
    for i in range(N-600,600,-1):
        for k in range(599,i-1):
            for t in range(k+1,i):
                if L[i] < L[k] + L[t]:
                    break
                else:
                    s -= 1

                
print(s)

Submission status: Runtime Error

Solution code:
N=int(input())
b=[]
L=[]
b=input().split()

for i in range(N):
    L.append(int(b[i]))
L.sort()
print(L)
x=0
index=0
for i in range(N-2):
    x=L[0]
    L.remove(L[0])
    for k in range(N-3):
        if (x + L[k]) > L[k+1]:
            index+=1
print(index)

Submission status: Runtime Error

Solution code:
N = int( input() )
list_t = list( map (int, input().split() )
counter = 0 
a = del list_t[0]
b = del list_t[0:2]
for i in list_t:
	for j in a:
		for k in b:
            if i == (len(list_t) - 3)
              break
            else:
              if i < j + k and j < i + k:
            	if k < i + j:
                	counter += 1
    a = del a[0]
    b = del b[0]

print ( counter )

Submission status: Runtime Error

Solution code:
n=int(input())
llist=list(map(int,input().split()))
kazoe=0

llist.sort()
for a in range(n-2):
	for b in range(a+1,n-1):
		sa=llist[b]-llist[a]
		wa=llist[a]+llist[b]

		y=b
		z=n
		x=(y+z)//2
		while llist[x]>wa or llist[x+1]<wa:	
			if wa>llist[x]:
				z=x
			elif wa<=llist[x]:
				y=x
			x=(y+z)//2
		kazoe+=x-b
print(kazoe)

Submission status: Runtime Error

Solution code:
N=int(input())
L=list(map(int,input().split()))
d=[]
s=0
def triagles(a,b,c):
  if a<b+c and b<a+c and c<a+b:
    d+=set([a,b,c])
    return 1
  else:
    return 0
for i in range(N):
  for j in range(N):
    for k in range(N):
      if i!=j and j!=k and k!=i:
        if set([L[i],L[j],L[k]]) not in d:
          s+=triangles([L[i],L[j],L[k]])
print(s)

Submission status: Runtime Error

Solution code:
n=int(input())
S=list(map(int, input().split()))
S.sort(reverse=True)
count=0
print(S)
for i in range(n-2):
    if(S[i]-S[n-1]-S[n-2])<0:
        break
    for j in reversed(range(i+2,n)):
        if(S[i]-S[j]-S[n])<0:
            break:
        for k in reversed(range(i+1,j)):
            if(S[i]>=S[j]+S[k]):
                count=count+1
            else:
                break
print(int(n*(n-1)*(n-2)/6-count))

Submission status: Runtime Error

Solution code:
N = str(input())
N = int(N)
Lines = input().split(" ")
Lines = list(map(int, Lines))
answer = 0

for lineI in range(len(N)):
    for lineJ in range(lineI+1,len(N)):
        for lineK in range(lineJ+1,len(N)):
             if (Lines[lineI] + Lines[lineJ] > Lines[lineK]) and (Lines[lineK] + Lines[lineJ] > Lines[lineI]) and (Lines[lineK] + Lines[lineI] > Lines[lineJ]):
                answer += 1
print(answer)

Submission status: Runtime Error

Solution code:
n = int(input())
l = list(map(int, input().split()))
l.sort()
count = 0
for i in range(n - 2):
    for j in range(n - i - 2):
        w = i + j + 2
        e = n - 1
        if l[i + j + 2] < l[i] + l[i + j + 1]:
            count += 1
        x = int((w + e) / 2)
        while l[x] > l[i] + l[i + j + 1] or l[x + 1] < l[i] + l[i + j + 1]:
            if l[x] > l[i] + l[i + j + 1]:
                e = x
            else:
                w = x
        count += x - i - j - 2
print(int(count))

Submission status: Runtime Error

Solution code:
N = str(input())
N = int(N)
Lines = input().split(" ")
Lines = list(map(int, Lines))
answer = 0

for lineI in range(len(N)):
    for lineJ in range(lineI+1,len(N)):
        for lineK in range(lineJ+1,len(N)):
             if (Lines[lineI] + Lines[lineJ] > LinesInt[lineK]) and (Lines[lineK] + Lines[lineJ] > Lines[lineI]) and (Lines[lineK] + Lines[lineI] > Lines[lineJ]):
                answer += 1
print(answer)

Submission status: Runtime Error

Solution code:
n = int(input)
ln = input().split()
s = 0

for i in range(n):
  for j in range(i + 1, n):
    for k in range(j + 1, n):
      if int(ln[i]) < int(ln[j]) + int(ln[k]) and int(ln[j]) < int(ln[k]) + int(ln[i]) and int(ln[k]) < int(ln[j]) + int(ln[i]):
        s += 1
        
pritn(s)

Submission status: Runtime Error

Solution code:
n = int(input())
l = list(map(int,input().split(" ")))
count = 0
l = sorted(l,reverse = True)
for i in range(n-2):
  i_over = False
  for j in range(i+1,n-1):
    for k in range(j + 1,n):
      if l[i] >= l[j]+l[k]:
        break
        count += 1
    if l[i] >= l[j+1]+l[j+2]:
      break 
print(count)

Submission status: Runtime Error

Solution code:
N = str(input())
N = int(N)
Lines = input().split(" ")
LinesInt = map(int, Lines)
answer = 0
    
for lineI in range(len(N)):
    for lineJ in range(lineI+1,len(N)):
        for lineK in range(lineJ+1,len(N)):
             if (LinesInt[lineI] + LinesInt[lineJ] > LinesInt[lineK]) and (LinesInt[lineK] + LinesInt[lineJ] > LinesInt[lineI]) and (LinesInt[lineK] + LinesInt[lineI] > LinesInt[lineJ]):
                answer += 1
print(answer)

Submission status: Runtime Error

Solution code:
# Atcoder 2019/10/19
"""
# A
A, B = map(int, input().split())

ans = A - 2 * B

if ans >= 0:
    print(ans)
else:
    print(0)
"""

"""
# B
import sys
n = int(input())
d = list(map(int, sys.stdin.readline().strip().split()))

ans = 0

for i in range(n - 1):
    for j in range(i + 1, n):
        ans += d[i] * d[j]

print(ans)
"""

"""
# C
n = int(input())
s = input()

count = 1

for i in range(len(s) - 1):
    if s[i] != s[i + 1]:
        count += 1

print(count)
"""

# D
import sys

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

    global big_ans
    big_ans = []

    def angle(l, count, ans, i, n):
        if len(ans) == 3:
            big_ans.append(ans)
            return ans

        if i == n:
            # print('i end')
            return

        if len(ans) + n - i < 3:
            return

        passa = ans.copy()
        angle(l, count, passa, i + 1, n)
        ans.append(l[i])
        passb = ans.copy()
        angle(l, count + 1, passb, i + 1, n)

    angle(l, 0, [], 0, len(l))

    ans_count = 0

    for i in big_ans:
        if sum(i) - 2 * max(i) > 0:
            ans_count += 1

    print(ans_count)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n=int(input())
S=list(map(int, input().split()))
S.sort(reverse=True)
count=0
print(S)
for i in range(n-2):
    if(S[i]-S[n-1]-S[n-2])<0:
        break
    for j in reversed(range(i+2,n)):
        if(S[i]-S[j]-S[n-2])<0:
            break:
        for k in reversed(range(i+1,j)):
            if(S[i]>=S[j]+S[k]):
                count=count+1
            else:
                break
print(int(n*(n-1)*(n-2)/6-count))

Submission status: Runtime Error

Solution code:
from operator import mulfrom 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: Runtime Error

Solution code:
import sys
from itertools import combinations
import bisect
import math
import numpy as np
n = int(input())
l_ls = [int(i) for i in sys.stdin.readline().split()]
l_ls.sort()
l_dict = { i : j for i, j in enumerate(l_ls)}
_sum_ls = []
cnt = 0
count_ls = np.zeros(2*10**3, dtype=np.int)
for l in l_ls:
    count_ls[:l+1] += 1
for combi in combinations(l_ls, 2):
    ind = count_ls[combi[0] + combi[1]]
    cnt += ind
"""
for combi in combinations(l_ls, 2):
    count_ls[combi[0] + combi[1]:] += 1
    #bisect.insort_left(_sum_ls, combi[0] + combi[1])
len_sum_ls = len(_sum_ls)
for l in l_ls:
    #ind = bisect.bisect_right(_sum_ls, l)
    ind = count_ls[l]
    cnt += ind
"""

print(int(math.factorial(n) / math.factorial(3) / math.factorial(n-3)) - cnt)