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:
from scipy.misc import comb
# a = comb(n, r)
# a = comb(n, r, exact=True)

n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
a = []
a.append(l[0])
cnt = 1
numMap = {}

for i in range(1, n):
    if l[i] == l[i-1]:
        cnt += 1
    else:
        if cnt > 2:
            numMap[l[i-1]] = cnt
        a.append(l[i])
        cnt = 1

numMap[l[-1]] = cnt

for i, val in numMap.items():
    #print(i, val)
    temp = comb(val, 3, exact=True)
    ans += temp

# print(a)
# print(numMap)
# print(ans)

for i in range(len(a)):
    for j in range(i+1, len(a)):
        length = a[i] + a[j]

        for k in range(j+1, len(a)):
            if a[k] >= length:
                break
            else:
                ans += numMap[a[i]] * numMap[a[j]] * numMap[a[k]]

print(ans)

Submission status: Runtime Error

Solution code:
from math import factorial
N=int(input())
L=input()
L=L.split()
L=[int(item) for item in L]
L.sort()
ans=factorial(N)/factorial(3)/factorial(N-3)
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]:
                ans-=(N-k)
                break


print(int(ans))

Submission status: Runtime Error

Solution code:
N = int(input())
L = list(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):
#      #print(str(i) + str(j) + str(k))
#      if L[i] < L[j] + L[k] and L[j] < L[k] + L[i] and L[k] < L[i] + L[j]:
#        ans += 1
#print(ans)
comb = list(itertools.combinations(L, 3))
print(comb)

Submission status: Runtime Error

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

from itertools import accumulate
from scipy.special import comb


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 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[b] == 0:
                cnt += int(comb(nums[b], 2))
                tmp2[b] = 1

            ans += cnt

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from scipy.special import comb
n = int(input())
h = list(map(int, input().split()))
def triangle(n,h):
    x = comb(n, 3, exact = True)
    for i in range(0,n-2):
        for j in range(i+1,n-1):
            for k in range(j+1, n):
                if h[i] >= h[j] + h[k] or h[j] >= h[i] + h[k] or h[k] >= h[j] + h[i]:
                    x = x - 1
    return x
print(triangle(n,h))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n = int(input())
l = list(map(int,input().split(" ")))
count = 0
l = sorted(l)
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]:
      break
      count += 1
print(count)

Submission status: Runtime Error

Solution code:
n = int(input())
l = list(map(int,input().split(" ")))
count = 0
l = sorted(l)
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]:
    break
    count += 1
print(count)

Submission status: Runtime Error

Solution code:
import bisect

N = int(input())
L = [int(v) for v in input().split()]
L.sort()

l = len(L)



def judge(a, b, c):
    if a >= b + c:
        return False
    if b >= c + a:
        return False
    if c >= a + b:
        return False
    return True

count = 0
for i in range(l):
    a = L[i]
    for j in range(i+1,l):
        b = L[j]
        ab = a + b
        count+=bisect.bisect_left(L[j+1,l],ab)
                
print(count)

Submission status: Runtime Error

Solution code:
import bisect

N = int(input())
L = [int(v) for v in input().split()]
L.sort()

l = len(L)



def judge(a, b, c):
    if a >= b + c:
        return False
    if b >= c + a:
        return False
    if c >= a + b:
        return False
    return True

count = 0
for i in range(l):
    a = L[i]
    for j in range(i+1,l):
        b = L[j]
        ab = a + b
        count+=bisect.bisect_left(L[i+1,l],ab)
                
print(count)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# 入力
N = int(input())
L = list(map(int, input().split()))

L.sort(reverse=True)
sum = 0
for i in range(N):
  half = L[i]/2.0
  for j in range(i+1, N):
    if(L[j] <= half):
      jend = j
  for j in range(i+1, jend):
    for k in range(j+1, N):
      if(L[i] < L[j] + L[k]):
        sum +=1

print("{}".format(sum))

Submission status: Runtime Error

Solution code:
# D TLE
import itertools
import bisect

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

L.sort()
value = 0

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

print(value)

Submission status: Runtime Error

Solution code:
def sarch(l, left, right, target):
    global ans, cnt
    cnt += 1
    if cnt > 100000:
        return 0
    mid = right + left
    mid //= 2
    print(left, right, target, mid, ans)
    if right - left <= 1:
        if l[right] >= target:
            return right
        if l[left] >= target:
            return left
        else:
            return 0
    if target < l[mid]:
        print(2)
        return sarch(l, mid, right, target)
    if target == l[mid]:
        return mid
    if l[mid] < target:
        print(1)
        return sarch(l, left, mid, target)

cnt = 0
n = int(input())
l = list(map(int, input().split()))
l.sort()
l = l[::-1]
# print(l)
ans = 0
l2 = []
for i in range(n - 1):
    for j in range(i, n):
        if i < j:
            l2.append(l[i] + l[j])
print(l2)
N = n
n = len(l2)

for i in range(n - 2):
    target = l[i] + 1
    tmp = sarch(l2, 0, n - 1, target)
    print(tmp, i)
    for j in range(tmp, n - 1):
        if l2[j] == l2[j + 1]:
            tmp += 1
        else:
            break
    tmp += 1
    if tmp > i:
        ans += (tmp - (N - 1))

print(ans)

Submission status: Runtime Error

Solution code:
import bisect
    
    n = int(input())
    length = list(map(lambda x:int(x), input().split()))
    length.sort()
    ans = 0
    for i in range(n):
        a = length[i]
        for j in range(n):
            b = length[j]
            if i >= j:
                continue
            else:
                c_candidates = length[j+1:]
                min_bar = bisect.bisect_right(c_candidates,max(a-b, b-a))
                max_bar = bisect.bisect_left(c_candidates,a+b)
                ans += max_bar - min_bar
                
    print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

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

array = np.sort(L)[::-1]

sum = 0

for i in array:
  for j in array[1::]:
    sum += np.count_nonzero(array[j+1::] > (array[i] - array[j]))
print(sum)

Submission status: Runtime Error

Solution code:
N = int(input())
L = list(map(int, input().split()))
l =sorted(L)
t = 0
for i in range(N-2):
  if i > 0 and l[i] = l[i-1]:
    break
  else:
    for k in range(i+1,N-1):
      for m in range(k+1, N):
        if l[m] < l[k] + l[i]:
          t += 1
        else:
          break
print(t)

Submission status: Runtime Error

Solution code:
n = int(input())
#a,b = map(int,input().split())
li = list(map(int,input().split()))
li.sort()
#print(li)
num = 0

for i in range(n-4):
    if li[i] == li[i+1] ==li[i+2] == li[i+3]:
        li.pop(li[i+3])
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if li[i]+li[j]>li[k] and li[i]<li[j]+li[k] and li[i]+li[k]>li[j]:
                num += 1
print(num)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
L = [int(l) for l in input().split()].sort()

total = 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]:
                total += 1
print(total)

Submission status: Runtime Error

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

from collections import Counter
c = Counter(l2)
k = list(c.keys())
k.sort()

from bisect import bisect_left, bisect_right
l2.sort()

ans = 0
for i in range(len(k)):
    for j in range(i+1, len(k)):
        c_min = k[j] - k[i]
        c_max = k[i] + k[j]

        idx = bisect_right(l2, k[j])
        tmp = l2[idx:]

        idx_min = bisect_right(tmp, c_min)
        idx_max = bisect_left(tmp, c_max)

        ans += max(0, idx_max - idx_min) * c[k[i]] * c[k[j]]

for _k in k:
    if c[_k] >= 2:
        idx = bisect_right(l2, _k)
        tmp = l2[idx:]
        idx_min = bisect_right(tmp, 0)
        idx_max = bisect_left(tmp, _k * 2)

        ans += max(0, idx_max - idx_min) * (c[_k] - 1) * c[k] // 2

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
#a,b = map(int,input().split())
li = list(map(int,input().split()))
li.sort()
#print(li)
num = 0

for i in range(n-4):
    if li[i] == li[i+1] ==li[i+2] == li[i+3]:
        li.pop(li[i+3])
for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):
            if li[i]+li[j]>li[k] and li[i]<li[j]+li[k] and li[i]+li[k]>li[j]:
                num += 1
print(num)

Submission status: Runtime Error

Solution code:
import itertools
from math import factorial

n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
original = a.copy()

count = [0]
daburi = []
c_list = []
c = 1

for i in range(2000):
    if a[0] > a[1] * 2:
        a.pop(0)

for i in range(len(a)-1):
    if a[i] == a[i+1]:
        if a[i] not in daburi:
            daburi.append(a[i])
        c += 1
    else:
        c_list.append(c)
        c = 1

for i in range(len(daburi)):
    if c_list[i] == 2:
        count[0] += n - original.index(2*daburi[i]-1) - 2
    else:
        count[0] += n - original.index(2 * daburi[i] - 1) - c_list[i]
        count[0] += factorial(c_list[i]) / factorial(3) /factorial(c_list[i] - 3)

a = sorted(set(a), key=a.index)

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

def check_triangle(li):
    li.sort(reverse=True)
    if li[0] < li[1] + li[2]:
        count[0] += 1


for i in x:
    check_triangle(list(i))

print(count[0])

Submission status: Runtime Error

Solution code:
from scipy.special import comb
# a = comb(n, r)
# a = comb(n, r, exact=True)

n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
a = []
a.append(l[0])
cnt = 1
numMap = {}

for i in range(1, n):
    if l[i] == l[i-1]:
        cnt += 1
    else:
        numMap[l[i-1]] = cnt
        a.append(l[i])
        cnt = 1

numMap[l[-1]] = cnt

for i, val in numMap.items():
    #print(i, val)
    temp = comb(val, 3, exact=True)
    ans += temp

# print(a)
# print(numMap)
# print(ans)

for i in range(len(a)):
    for j in range(i+1, len(a)):
        length = a[i] + a[j]

        for k in range(j+1, len(a)):
            if a[k] >= length:
                break
            else:
                ans += numMap[a[i]] * numMap[a[j]] * numMap[a[k]]

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
#a,b = map(int,input().split())
li = list(map(int,input().split()))
li.sort()
#print(li)
num = 0

for i in range(n-4):
    if li[i] == li[i+1] ==li[i+2] == li[i+3]:
        li.pop(li[i])
for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):
            if li[i]+li[j]>li[k] and li[i]<li[j]+li[k] and li[i]+li[k]>li[j]:
                num += 1
print(num)

Submission status: Runtime Error

Solution code:
n = int(input())
#a,b = map(int,input().split())
li = list(map(int,input().split()))
li.sort()
#print(li)
num = 0

for i in range(n-4):
    if li[i] == li[i+1] ==li[i+2] == li[i+3]:
        li.remove(li[i])
for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):
            if li[i]+li[j]>li[k] and li[i]<li[j]+li[k] and li[i]+li[k]>li[j]:
                num += 1
print(num)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
import itertools
N = int(input())
L = list(map(int, input().split()))
num = []
ans = 0

for i in itertools.permutations(L, r=3):
    i = list(i)
    i.sort()
    if i not in num:
        num.append(i)

for i in range(len(num)):
    if num[i][0] + num[i][1] > num[i][2]　and num[i][1] + num[i][2] > num[i][0] and num[i][0] + num[i][2] > num[i][1]:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
#include <iostream>

using namespace std;

int main(){
	
	int N = 0;
	cin >> N;
	int L[N] = {0};
	for(int i=0; i<N; i++){
		cin >> L[i];
	}
	int c = 0;
	for( int i=0; i<N-2; i++ ){
		for( int j=i+1; j<N-1; j++ ){
			int s = L[i] + L[j];
			for( int k=j+1; k<N; k++ ){
				int s1 = L[k] + L[j], s2 = L[k] + L[i];
				if( s <= L[k] ){
					continue;
				}
				if( s1 <= L[i] || s2 <= L[j] ){
					continue;
				}
				c++;
			}
		}
	}
	cout << c << endl;
	return 0;
}

Submission status: Runtime Error

Solution code:
n=int(input())
List = [int(i) for i in input().split()]
List2=sorted(List)
ans = 0

for i in range(1,n-1): #aにたいし
  for j in range(i,n):
    tmp1 = List[i]
    tmp2 = List[j]
    
    ans += 4- bisect.bisect_right(List2,tmp1+tmp2)
    
print(ans)

Submission status: Runtime Error

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

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

# solve
ans = 0
L.sort()
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        for k in range(k + 1, N):
            if L[k] < L[j] + L[i]:
                ans += 1

# output
print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
L=list(map(int,input().split()))
counter=0
for t in range(N):
  for i in range(t+1,N):
    for p in range(i+1,N):
      if L[p]<L[t]+L[i] and L[t]<L[i]+L[p] and L[i]<L[p]+L[t]:
        counter+=1
print(counter

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N=int(input())
L=tuple(map(int,input().split()))
l=[0]*1001
g=[0]*1001
for i in L:
    l[i]+=1
for i in range(1,1001):
    g[i]=g[i-1]+l[i]
a=0
for i in range(1,999):
    for j in range(i+1,1000):
        a+=l[i]*l[j]*(g[min(i+j-1,1000)]-g[j])
for i in range(1,1001):
    if l[i]>1:
        t=l[i]*(l[i]-1)//2
        for j in range(1,i):
            a+=t*l[j]
        if l[i]>2:
            a+=t*(l[i]-2)//3
        for j in range(i+1,min(1001,l[i*2])):
            a+=t*l[j]
print(a)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

# 2辺の和リスト
d = [0] * (l[-1] * 2)
ans = 0

for i in range(n):
  for val in d[l[i] + 1:]:
    # 長さd[i]より小さい組み合わせはOK
    ans += val

  # 自身との組み合わせをdに追加
  for j in range(i):
    d[l[i] + l[j]] += 1

print(ans)

Submission status: Runtime Error

Solution code:
	result = -1
	left = 0
	right = len(ls) - 1
	while left <= right:
		center = (left + right)//2
		if ls[center] == target:
			result = center-1
			break
		elif ls[center] < target:
			right = center - 1
		elif ls[center] > target:
			left = center + 1
	if result == -1:
		return left
	else:
		return result

from collections import deque
N=int(input())
l=list(map(int,input().split()))
l.sort(reverse=True)
c=0
for i in range(N-2):
  for j in range(i+1,N-1):
    c+=binary_search(l[j+1:],l[i]-l[j])
print(c)

Submission status: Runtime Error

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

def aaa(l):
    x=0
    a=l[0]
    b=l[1]
    c=l[2]
    if a+b>c:
        if b+c>a:
            if c+a>b:
                x=1
    return x
ans=0
for l in list(itertools.combinations(L, 3)):
    ans+=aaa(list(l))
print(ans)

Submission status: Runtime Error

Solution code:
if __name__ == '__main__':
    n = int(input())
    l = [int(i) for i in input().split()]
    l.sort(reverse=True)
    index = list(range(10))
    list_dict = dict(zip(index, l))

    ans = 0
    for i in range(n):
        li = list_dict[i]
        if i > n-1:
            break
        for j in range(n):
            lj=list_dict[j]
            if j>i:
                if j > n:
                    break
                for k in range(n):
                    lk = list_dict[k]
                    if k > j:
                        if li < lj+ lk:
                            ans = ans +1
                        else:
                            break
    print(ans)

Submission status: Runtime Error

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

import itertools

s_list= list(itertools.combinations(d_list, 3))
count = 0
for s in s_list:
  a, b, c = sa
  if (a < b + c) and (b < c + a) and (c < a + b):
    count+=1
print(count)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
n=int(input().rstrip())
l=input().split(" ")
for i in range(n):
    l[i]=int(l[i])
l=sorted(l)
//print(l)
ans = 0;
a=0
b=1
c=2
while(1):
    while(1):
        while(1):
            if(l[a]<l[b]+l[c] and l[b]<l[a]+l[c] and l[c]<l[a]+l[b]):
                ans=ans+1
                c= c+1;
                if(c >=n):
                    break
            else:
                break
        b=b+1
        c=b+1
        if(c >=n):
            break
    a=a+1
    b=a+1
    c=b+1
    if(c>=n):
        break
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
d = list(map(int, input().split()))
d.sort()
count = 0
for i in range(len(d)):
    j = i + 1
    for j in range(i + 1, len(d)):
        k = j + 1
        for k in range(j + 1, len(d)):
            if d[i] + d[j] <= d[k]:
                break
            count += 1
        if k == j+1:
            break
    if j == i + 1
    break
print(count)

Submission status: Runtime Error

Solution code:
s = input().split()
n=int(s[0])
s = input().split()
s=list(itertools.combinations(s, 3))
count=0
for i in s:
    if int(i[0]) < int(i[1])+int(i[2]) and int(i[1]) < int(i[0])+int(i[2]) and int(i[2]) < int(i[1])+int(i[0]):
        count+=1

print(count)

Submission status: Runtime Error

Solution code:
def main():
	import sys
	input = sys.stdin.readline
	
	n = int(input())
	arr = sorted(map(int, input().split()))
	
	ans = 0
	for i in range(2, n):
		r = 1
		for l in range(i - 1):
			while r <= l || arr[l] + arr[r] <= arr[i]:
				r += 1
			
			ans += i - r
	
	print(ans)
	
	return 0

main()

Submission status: Runtime Error

Solution code:
n=int(input())
l=list(map(int,input().split()))
l.sort()
ans = 0
for i  in range(n-2):
    if l[i]==a:
        continue
    a = l[i]
    b = 0
    for j in range(i+1,n-1):
        if l[j]==b:
            continue
        b = l[j]
        c = 0 
        for k in range(j+1,n):
            if l[k]==c:
                continue
            c = l[k]
            if c-b < a:
                ans += 1
            else:
                break
print(ans)

Submission status: Runtime Error

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

L_len = len(L)

count = 0
for i in range(L_len - 2):
    for j in range(i + 1, L_len - 1):
        for k in range(j + 1, L_len):
            f = 0
            if a >= b + c:
                f = 1
            if b >= a + c:
                f = 1
            if c >= a + b:
                f = 1
            
            if f == 0:
                count += 1

print(count)

Submission status: Runtime Error

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

value = 0
for i in itertools.combinations(L, 3):
    a, b, c = i
    
    if a<b+c:
        if b<c+a:
            if c<a+b:
                value+=1
print(value)