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 bisect

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

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

print(ans)

Submission status: Time Limit Exceeded

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

l.sort()
l.reverse()
ans=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]:
                ans+=1
            else:
                break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

n = int(input())
L = sorted(map(int, input().split()))
ans = 0
for i in range(n-2):
    a = L[i]
    for j in range(i+1, n-1):
        b = L[j]
        l = bisect.bisect(L[j+1:n], a+b-1)
        ans += l
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
L = sorted(map(int, input().split()))
ans = 0
for i in range(n-2):
    a = L[i]
    for j in range(i+1, n-1):
        b = L[j]
        k = j + 1
        cnt = 0
        while k <= n - 1:
            if L[k] >= a + b:
                break
            k += 1
            cnt += 1
        ans += cnt
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = sorted(list(map(int,input().split())),reverse=True)
#print (l)

ans = 0
for i in range(n-1):
    for j in range(i+1,n):
#        print (l[i],l[j],l[j+1::],[x for x in l[j+1::] if x < l[i]+l[j] and l[i] < x+l[j] and l[j] < x+l[i]])
        ans += len([x for x in l[j+1::] if x < l[i]+l[j] and l[i] < x+l[j] and l[j] < x+l[i]])


print (ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

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

ans = 0

for a, b, c in combinations(L, 3):
    if a >= b + c:
        continue
    elif b >= a + c:
        continue
    elif c >= a + b:
        continue
    else:
        ans += 1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    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):
            a = l[i]
            b = l[j]
            k = j + 1
            while k < n and l[k] < a + b:
                ans += 1
                k += 1

    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Time Limit Exceeded

Solution code:
inf = 1001001001
n = int(input())
lis = list(map(int, input().split()))
lis.sort()
lis.append(inf)
ans = 0
for i in range(n-2):
    a = lis[i]
    for j in range(i + 1, n-1):
        b = lis[j]
        l = j
        r = n
        while r > l+1:
            mid = (l+r) // 2
            if lis[mid] < a + b:
                l = mid
            else:
                r = mid
        ans += l - j
print(ans)

Submission status: Time Limit Exceeded

Solution code:
inf = 1001001001
n = int(input())
lis = list(map(int, input().split()))
lis.sort()
ans = 0
for i in range(n-1):
    a = lis[i]
    for j in range(i + 1, n):
        b = lis[j]
        nl = lis[j:]
        nl.append(inf)
        l = 0
        r = n-j
        while r > l+1:
            mid = (l+r) // 2
            if nl[mid] < a + b:
                l = mid
            else:
                r = mid
        ans += l
print(ans)

Submission status: Time Limit Exceeded

Solution code:
inf = 1001001001
n = int(input())
lis = list(map(int, input().split()))
lis.sort()
ans = 0
for i in range(n-1):
    a = lis[i]
    for j in range(i + 1, n):
        b = lis[j]
        nl = lis[j:] + [inf]
        l = 0
        r = n-j
        while r > l+1:
            mid = (l+r) // 2
            if nl[mid] < a + b:
                l = mid
            else:
                r = mid
        ans += l
print(ans)

Submission status: Time Limit Exceeded

Solution code:
inf = 1001001001
n = int(input())
lis = list(map(int, input().split()))
lis.sort()
ans = 0
for i in range(n-1):
    a = lis[i]
    for j in range(i + 1, n):
        b = lis[j]
        nl = lis[j:] + [inf]
        l = 0
        r = len(nl) -1
        while r > l+1:
            mid = (l+r) // 2
            if nl[mid] < a + b:
                l = mid
            else:
                r = mid
        ans += l
print(ans)

Submission status: Time Limit Exceeded

Solution code:
inf = 1001001001
n = int(input())
lis = list(map(int, input().split()))
lis.sort()
ans = 0
for i in range(n-1):
    a = lis[i]
    for j in range(i + 1, n):
        b = lis[j]
        nl = [0] + lis[j+1:] + [inf]
        l = 0
        r = len(nl) -1
        while r > l+1:
            mid = (l+r) // 2
            if nl[mid] < a + b:
                l = mid
            else:
                r = mid
        ans += l
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
import copy
from itertools import combinations


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

li = list(combinations(l, 2))


ans = 0
for i in li:
    x = copy.deepcopy(l)
    x.remove(i[0])
    x.remove(i[1])
    left = abs(i[0] - i[1])
    small = min(i[0], i[1])
    x = [i for i in x if i < small]

    if len(x) != 0:
        left_div = bisect_left(x, left+1)
        ans += max(0, len(x) - left_div)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
import copy
from itertools import combinations


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

li = list(combinations(l, 2))


ans = 0
for i in li:
    x = copy.deepcopy(l)
    x.remove(i[0])
    x.remove(i[1])
    left = abs(i[0] - i[1])
    right = min(i[0], i[1])

    left_div = bisect_left(x, left+1)
    right_div = bisect_right(x, right-1)
    ans += max(0, right_div - left_div)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import copy
from itertools import combinations


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

li = list(combinations(l, 2))


ans = 0
for i in li:
    x = copy.deepcopy(l)
    x.remove(i[0])
    x.remove(i[1])
    left = abs(i[0] - i[1])
    right = min(i[0], i[1])

    left_div = bisect.bisect_left(x, left+1)
    right_div = bisect.bisect_right(x, right-1)
    ans += max(0, right_div - left_div)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations


def solve(a, b, c):
    x = a < b + c
    y = b < c + a
    z = c < a + b

    return all([x, y, z])


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

li = list(combinations(l, 3))

ans = 0
for a, b, c in li:
    if solve(a, b, c):
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
tris = list(map(int,input().split()))
tris.sort()
cnt = 0
for i in range(n-2):
    a = tris[i]
    for j in range(i+1,n-1):
        b = tris[j]
        # r = bisect.bisect_left(tris, a+b)
        # cnt += r - j - 1

        ok = j
        ng = n
        while abs(ok-ng) > 1:
            mid = (ok+ng) // 2
            if tris[mid] < a + b:
                ok = mid
            else:
                ng = mid
        cnt += ok - j
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
"""
二分探索

pythonでTLE, pypyでAC
"""

import sys
sys.setrecursionlimit(10**6)

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

L.sort()
ans = 0

for i in range(n-2):
    l_prev = 0
    for j in range(i+1,n-1):
        if not l_prev:
            l = j; r = n # 前のループで探索した範囲は探索不要なのでもっと高速化できるはず
        else:
            l = l_prev; r = n
        while l+1 < r:
            c = (l+r)//2
            if L[c] < L[i]+L[j]:
                l = c
            else:
                r = c
        ans += l-j
        l_prev = l
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
N = int(input())
L = sorted(list(map(int, input().split())))

ans = 0
for i in range(N-2):  # １番短い棒 #どうせ増えないからＮでも多分大丈夫
  for j in range(i + 1, N-1):  # 真ん中の長さの棒
    ans += bisect_left(L[j+1:], L[i] + L[j]) 

print(ans)

Submission status: Time Limit Exceeded

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

for i in range(N-2):
  for j in range(i+1,N-1):
    x = L[i]+L[j]
    B = N-1
    A = j
    max_c_index = j
 #   while True:
    while A <= B: #A>Bとなったときに停めるようにすれば簡潔
     # M = A + (B-A)//2
      M = (A+B)//2 #こう書くほうがシンプル
      if L[M] < x:
        max_c_index = M
        A = M+1
      else:
#        B = M
        B = M-1
    value += max_c_index - j
print(value)

Submission status: Time Limit Exceeded

Solution code:
"""二分探索"""

import sys
sys.setrecursionlimit(10**6)

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):
        l = j; r = n
        while l+1 < r:
            c = (l+r)//2
            if L[c] < L[i]+L[j]:
                l = c
            else:
                r = c
        ans += l-j
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
tris = list(map(int,input().split()))
tris.sort()
cnt = 0
for i in range(n-2):
    a = tris[i]
    for j in range(i+1,n-1):
        b = tris[j]

        low = j
        high = n
        while high - low > 1:
            mid = low + (high - low) // 2
            c = tris[mid]
            if c < a + b:
                low = mid
            else:
                high = mid
        cnt += low - j
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
tris = list(map(int,input().split()))
tris.sort()
cnt = 0
for i in range(n-2):
    a = tris[i]
    for j in range(i+1,n-1):
        b = tris[j]
        low = j
        high = n
        while high - low > 1:
            mid = low + (high - low) // 2
            c = tris[mid]
            if a < b + c and b < c + a and c < a + b:
                low = mid
            else:
                high = mid
        cnt += low - j
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
tris = list(map(int,input().split()))
tris.sort()
cnt = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        low = j
        high = n
        while high - low > 1:
            mid = low + (high - low) // 2
            if tris[i] < tris[j] + tris[mid] and tris[j] < tris[i] + tris[mid] and tris[mid] < tris[i] + tris[j]:
                low = mid
            else:
                high = mid
        cnt += low - j
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
tris = list(map(int,input().split()))
tris.sort()
cnt = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        low = j
        high = n
        while high - low > 1:
            mid = (high + low) // 2
            if tris[i] < tris[j] + tris[mid] and tris[j] < tris[i] + tris[mid] and tris[mid] < tris[i] + tris[j]:
                low = mid
            else:
                high = mid
        cnt += low - j
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
tris = list(map(int,input().split()))
tris.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 tris[i] < tris[j] + tris[k] and tris[j] < tris[k] + tris[i] and tris[k] < tris[i] + tris[j]:
                cnt += 1
            else:
                break
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
tris = list(map(int,input().split()))
cnt = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if tris[i] < tris[j] + tris[k] and tris[j] < tris[k] + tris[i] and tris[k] < tris[i] + tris[j]:
                cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

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

cnt = 0
for c in range(n):
    for b in range(c+1,n):
        mina = l[b]-l[c]
        maxa = l[b]+l[c]
        for a in range(b+1,n):
            if(l[a] >= maxa):
                break
            cnt+=1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = list(map(int,input().split()))
l.sort()
from itertools import combinations

cnt = 0
for c in range(n):
    for b in range(c+1,n):
        mina = l[b]-l[c]
        maxa = l[b]+l[c]
        for a in range(b+1,n):
            t = l[a]
            if(mina < t and t < maxa):
                cnt+=1
"""
for x,y in combinations(range(n),2):
    if(x > y):
        b = x
        c = y
    else:
        c = x
        b = y
    for a in range(b+1,n):
        t = l[a]
        if((l[b]-l[c]) < t and t < (l[b]+l[c])):
            cnt += 1
"""
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = list(map(int,input().split()))
l.sort()
from itertools import combinations

cnt = 0
for x,y in combinations(range(n),2):
    if(x > y):
        b = x
        c = y
    else:
        c = x
        b = y
    for a in range(b+1,n):
        t = l[a]
        if((l[b]-l[c]) < t and t < (l[b]+l[c])):
            cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

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

from itertools import combinations

l.sort()
ans = 0
combs = set(combinations(l,3))

for c in combs:
    if c[0]+c[1]>c[2] and c[1]+c[2]>c[0] and c[2]+c[0]>c[1]:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

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

from itertools import combinations

l.sort()
ans = 0
seen = set()

for c in list(combinations(l,3)):
    if c not in seen:
        seen.add(c)
        if c[0]+c[1]>c[2] and c[1]+c[2]>c[0] and c[2]+c[0]>c[1]:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

for i in range(N-2):
  for j in range(i+1,N-1):
    x = L[i]+L[j]
    B = N-1
    A = j
    max_c_index = j
    while True:
      M = A + (B-A)//2
      if B-A<=1:
        if L[B] < x:
          max_c_index = B
        value += max_c_index - j
        break
      if L[M] < x:
        max_c_index = M
        A = M       
      else:
        B = M
print(value)

Submission status: Time Limit Exceeded

Solution code:
value = 0
N = int(input())
L = list(map(int,input().split()))
L = sorted(L)
a_plus_b = [] 
for i in range(1,N-1):
  for j in range(i):
    a_plus_b.append(L[j]+L[i])

for i in range(2,N):
  for j in range(i*(i-1)//2):
    if L[i] < a_plus_b[j]:
      value += 1
print(value)

Submission status: Time Limit Exceeded

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

L.sort()

def check(x,y,z):
    if x+y>z:
        return True
    else:
        return False

ans = 0
for a in range(N-2):
    for b in range(a+1, N-1):
        right = N
        left  = b
        while (right-left)>1:
            mid = (right+left)//2
            if check(L[a], L[b], L[mid]):
                left = mid
            else:
                right  = mid

        if left!=b:
            ans = ans + left - b

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n = int(input())
l = list(map(int,input().split()))
ans = 0

p = itertools.combinations(l,3)
for v in p:
    if v[0] < v[1] + v[2] and v[1] < v[0] + v[2] and v[2] < v[0] + v[1]:
        ans += 1

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):
    a = L[i]
    for j in range(i+1,n):
        b = L[j]
        for k in range(j+1,n):
            c = L[k]
            if a<b+c and b<c+a and c<a+b:
                ans+=1
print(ans)

Submission status: Time Limit Exceeded

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

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

List.sort()

a = []

for i in range(N):
  for j in range(i+1,N):
    a.append(List[i] + List[j])
    
a.sort()
ans = N * (N-1) * (N-2) / 6

for i in range(len(a)):
  b = a[i]
  c = bisect.bisect_left(List, b)
  ans -= (N-c)

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
# a < b + c
# b < a + C
# c < a + b

# 4 3 2 1
# a b c 

# abs(a - b) < c < a + b
# a < b < c
# b - a < b < c
# c < a + b 

from math import ceil, floor
from bisect import bisect_left, bisect_right

def solution(N, data): # O(N^2 * logN)
    data.sort()
    c = 0
    for i in range(N-2):
        for j in range(i+1, N-1):
            # c += bisect_left(data, data[i] + data[j], j) - j - 1
            c += bisect_left(data[j+1:], data[i] + data[j])


    return c

if __name__ == '__main__':
    N = int(input())
    L_i = list(map(int, input().split()))
    a = solution(N, L_i)
    print(a)

Submission status: Time Limit Exceeded

Solution code:
# a < b + c
# b < a + C
# c < a + b

# 4 3 2 1
# a b c 

# abs(a - b) < c < a + b
# a < b < c
# b - a < b < c
# c < a + b 

from math import ceil, floor
from bisect import bisect_left, bisect_right

def solution(N, data): # O(N^2 * logN)
    data = sorted(data)
    c = 0
    for i in range(N-2):
        for j in range(i+1, N-1):
            c += bisect_left(data[j+1:], data[i] + data[j])

    return c

if __name__ == '__main__':
    N = int(input())
    L_i = list(map(int, input().split()))
    a = solution(N, L_i)
    print(a)

Submission status: Time Limit Exceeded

Solution code:
# a < b + c
# b < a + C
# c < a + b

# 4 3 2 1
# a b c 

# abs(a - b) < c < a + b
# a < b < c
# b - a < b < c
# c < a + b 

from math import ceil, floor
from bisect import bisect_left, bisect_right

def solution(N, data): # O(N^2 * logN)
    data = sorted(data)
    c = 0
    for i in range(N):
        for j in range(i+1, N-1):
            max_t = data[i] + data[j]
            max_i = bisect_right(data[j+1:], max_t-1)

            c += max_i

    return c

if __name__ == '__main__':
    N = int(input())
    L_i = list(map(int, input().split()))
    a = solution(N, L_i)
    print(a)

Submission status: Time Limit Exceeded

Solution code:
# a < b + c
# b < a + C
# c < a + b

# 3 4 2 1
# a b c 

# abs(a - b) < c

def solution(N, data): # O(N^2 * logN)
    data = sorted(data)
    c = 0
    for i in range(N):
        for j in range(i+1, N-1):
            min_t = abs(data[i] - data[j])
            min_i = bisect_left(data[j+1:], min_t+1)
            max_t = data[i] + data[j]
            max_i = bisect_right(data[j+1:], max_t-1)
            # print(f'i: {i}, j: {j}, min_i: {min_i}, max_i: {max_i}')

            c += max_i - min_i

    return c

from math import ceil, floor
from bisect import bisect_left, bisect_right

if __name__ == '__main__':
    N = int(input())
    L_i = list(map(int, input().split()))
    a = solution(N, L_i)
    print(a)

    # a = bisect_right([4], 5)
    # b = bisect_left([4], 5)

    # print(a)
    # print(b)

    # a = binary_search_min_index([3, 4, 7, 8], 2)
    # print(a)

Submission status: Time Limit Exceeded

Solution code:
def  isOk(arg):
    if arg > mn:
        return True
    else:
        return False

def bisect_m(ng,ok):
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if isOk(l[mid]):
            ok = mid
        else:
            ng = mid
    return ok

n = int(input())
l = list(map(int,input().split()))
l.sort()
ans = 0
for i in range(n-2):
    a = l[n-1-i]
    for j in range(i+1,n-1):
        b = l[n-1-j]
        #print(a,b)
        mn = a - b
        ng = -1
        ok = n-1-j
        ok = bisect_m(ng,ok)
        ans += n-1-j - ok
        #print(a,b,l[ok],mn,ok)


print(ans)

Submission status: Time Limit Exceeded

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

INF = 2 * 10 ** 3 + 1

def main():
    N = int(input())
    L = [int(i) for i in input().split()]
    L.sort()

    # True ---- False
    def is_ok_top(mid: int, a: int, b: int):
        # 検索対象の外にあるものは先に弾く(リストのインデックスなんかだとout of rangeするので)
        if mid < 0:
            return True
        elif mid >= N:
            return False
        return L[mid] < L[a] + L[b]

    def binSearch_top(ok: int, ng: int, a: int, b: int):
        #print(ok, ng)              # はじめの2値の状態
        while abs(ok - ng) > 1:     # 終了条件（差が1となり境界を見つけた時)
            mid = (ok + ng) // 2
            if is_ok_top(mid, a, b):
                ok = mid            # midが条件を満たすならmidまではokなのでokの方を真ん中まで持っていく
            else:
                ng = mid            # midが条件を満たさないならmidまではngなのでngの方を真ん中まで持っていく
            #print(ok, ng)          # 半分に切り分ける毎の2値の状態
        return ok    

    count = 0
    for a in range(0, len(L) - 2):
        for b in range(a + 1, len(L) - 1):
            count += binSearch_top(-1, INF, a, b) - b

    print(count)







if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())

l = np.array([int(i) for i in input().split()])
l.sort()

c = np.bincount(l,minlength = 2100)

cum = list(c.cumsum())

ans = 0
for i in range(n):
    for j in range(i+1, n):
        ans += cum[min(l[i]+l[j]-1, 1000)] - (j+1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())

l = np.int32(input().split())
l.sort()

c = np.bincount(l,minlength = 2100)

cum = c.cumsum()

ans = 0
for i in range(n):
    for j in range(i+1, n):
        ans += cum[min(l[i]+l[j]-1, 1000)] - (j+1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = list(map(int,input().split()))
l.sort()
ans = 0
for i in range(n-2):
    a = l[n-1-i]
    for j in range(i+1,n-1):
        b = l[n-1-j]
        #print(a,b)
        mn = a - b
        ng = -1
        ok = n-1-j
        if mn >= b:
            continue
        while abs(ok - ng) > 1:
            hf = (ng + ok) // 2
            #print(a,b,l[hf])
            if l[hf] > mn:
                ok = hf
            else:
                ng = hf
        ans += n-1-j - ok
        #print(a,b,l[ok],mn,ok)


print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

N = int(input())
L = list(map(int, input().split()))
L.sort()
cnt = 0
#Flag = True

for i in range(N-2):
  for j in range(i+1, N-1):
    k = j + 1
    while L[k-1] == L[k]:
      if k == N-1:
        k = j + 1
        break
      k += 1
    #print(i, j, k)
    cnt += bisect_left(L, L[i]+L[j]) - k
    #print(cnt)

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# ABC143 D Triangles

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

l_list.sort()
ans = 0

# (i < j < k) -> (_a < _b < _c)
for i in range(n-2):
    _a = l_list[i]
    for j in range(i+1,n-1):
        _b = l_list[j]
        _tmp = _a + _b
        for k in range(j+1,n):
            _c = l_list[k]
            if _c < _tmp:
                ans += 1
            else:
                break

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):
    for j in range(N):
        for k in range(N):
            if i != j and i != k and j != 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(L[i],L[j],L[k])

print(ans//6)

Submission status: Time Limit Exceeded

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

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

print(ans//6)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
ans=0
for i in range(n):
  for j in range(i+1,n):
    k = j + 1
    while k < n and a[i] < a[j] + a[k]:
      k += 1
      ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:

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

L.sort()
#print(L)

count = 0
for i in range(N-1):
    for j in range(i+1, N-1):
        L_ = L[j+1:]
        #print(L[i] + L[j], ">", L_, "?")
        key = len(L_) // 2
        #print("init key", key)
        past_key = 0
        while key:
            if L[i] + L[j] > L_[key]:
                key = key + round((len(L_) - key) / 2)
            elif L[i] + L[j] <= L_[key]:
                key = round(key / 2)
            
            if past_key == key:
                break
            else:
                past_key = key
            #print("next key", key)
            
        if L[i] + L[j] > L_[key]:
            count += key + 1
            

print(count)

Submission status: Time Limit Exceeded

Solution code:

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

L.sort()
#print(L)

count = 0
for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            #print(i, j, k)
            #print(L[i], L[j], L[k])
            #print(L[i] + L[j] > L[k])
            if L[k] >= L[i] + L[j]:
                break
            count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:

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

import itertools
com = list(itertools.combinations(L, 3))

count = 0
for i in com:
    #print(i)
    if (i[0] < i[1] + i[2]) and (i[1] < i[0] + i[2]) and (i[2] < i[1] + i[0]):
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import collections
import itertools as it
import math
#import numpy as np
 
#  = input()
n  = int(input())
#  = map(int, input().split())
l  = list(map(int, input().split()))
#  = [int(input()) for i in range(N)]
#
# c = collections.Counter()

l = sorted(l)
#print(l)

ans = 0
for i1 in range(len(l)-2):
    a = l[i1]
    if a >= l[i1+1] + l[i1+2]:
        continue

    for i2 in range(i1+1, len(l)-1):
        b = l[i2]
        if b >= a + l[i2+1]:
            continue

        for i3 in range(i2+1, len(l)):
            if l[i3] < a + b:
                #print(a, b, l[i3])
                ans += 1
            else:
                break

        #l_ = [l[i3] for i3 in range(i2+1, len(l[i2+1:]))]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import collections
import itertools as it
import math
#import numpy as np
 
#  = input()
n  = int(input())
#  = map(int, input().split())
l  = list(map(int, input().split()))
#  = [int(input()) for i in range(N)]
#
# c = collections.Counter()

l = sorted(l)

ans = 0
for i1 in range(len(l)):
    for i2 in range(i1+1, len(l)):
        for i3 in range(i2+1, len(l)):
            a = l[i1]
            b = l[i2]
            c = l[i3]
            if c < a + b:
                ans += 1
            else:
                break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import collections
import itertools as it
import math
#import numpy as np
 
#  = input()
n  = int(input())
#  = map(int, input().split())
l  = list(map(int, input().split()))
#  = [int(input()) for i in range(N)]
#
# c = collections.Counter()

l = sorted(l)[::-1]

ans = 0
for i1 in range(len(l)):
    for i2 in range(i1+1, len(l)):
        for i3 in range(i2+1, len(l)):
            l_ = sorted([l[i1], l[i2], l[i3]])[::-1]
            if l_[0] < l_[1] + l_[2]:
                ans += 1
            else:
                break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import collections
import itertools as it
import math
#import numpy as np
 
#  = input()
n  = int(input())
#  = map(int, input().split())
l  = list(map(int, input().split()))
#  = [int(input()) for i in range(N)]
#
# c = collections.Counter()

l = sorted(l)[::-1]

ans = 0
for i1 in range(len(l)-2):
    a = l[i1]
    if a >= l[i1+1] + l[i1+2]:
        continue
    for i2 in range(i1+1, len(l)-1):
        b = l[i2]
        if b >= a + l[i2+1]:
            continue
        for i3 in range(i2+1, len(l)):
            c = l[i3]
            if a < b + c and b < c + a:
                if c < a + b:
                    ans += 1
                else:
                    break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import collections
import itertools as it
import math
#import numpy as np
 
#  = input()
n  = int(input())
#  = map(int, input().split())
l  = list(map(int, input().split()))
#  = [int(input()) for i in range(N)]
#
# c = collections.Counter()

l = sorted(l)[::-1]

ans = 0
for i1 in range(len(l)):
    for i2 in range(i1+1, len(l)):
        for i3 in range(i2+1, len(l)):
            a = l[i1]
            b = l[i2]
            c = l[i3]
            if a < b + c and b < c + a:
                if c < a + b:
                    ans += 1
                else:
                    break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import collections
import itertools as it
import math
#import numpy as np
 
#  = input()
n  = int(input())
#  = map(int, input().split())
l  = list(map(int, input().split()))
#  = [int(input()) for i in range(N)]
#
# c = collections.Counter()

l = sorted(l)

ans = 0
for i1 in range(len(l)):
    for i2 in range(i1+1, len(l)):
        for i3 in range(i2+1, len(l)):
            a = l[i1]
            b = l[i2]
            c = l[i3]
            if a < b + c and b < c + a and c < a + b:
                ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def is_ok(arg):
  #問題の定義
  return l[i]-l[j] < l[arg]
 
def nibutan(ng,ok):
  while (abs(ok-ng)>1):
    mid = (ok+ng)//2
    if is_ok(mid):
      ok = mid
    else:
      ng = mid
  return ok

n = int(input())
l = list(map(int,input().split()))
c = 0
l.sort(reverse=True)
for i in range(n-2):
  for j in range(i+1,n-1):
    a = nibutan(n,j)
    c += a-j
print(c)