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: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def printlist(lst, k='\n'): return k.join(list(map(str, lst)))
INF = float('inf')
import bisect

def solve():
    n = II()
    L = LI()
    L = sorted(L)

    ans = 0
    for i in range(n):
        li = L[i]
        for j in range(i+1, n):
            lj = L[j]
            ab = li + lj
            l_idx = j + 1
            r = li + lj
            # c = [l_idx, r_idx)
            r_idx = bisect.bisect_left(L, r)
            # print(li, lj, l_idx, r_idx)
            ans += r_idx - l_idx
    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import itertools
n=int(input())
l=list(map(int,input().split()))
l.sort()
nag=[0]*(10**3+1)
for i in range(n):
    nag[l[i]]+=1
rnag=list(itertools.accumulate(nag))
s=0
for j in range(n):
    for k in range(j+1,n):
        a,b=(l[j],l[k])
        if abs(a-b)<a+b-1<=10**3:
            s+=rnag[a+b-1]-rnag[abs(a-b)]
            if abs(a-b)<a<=a+b-1:
                s-=1
            if abs(a-b)<b<=a+b-1:
                s-=1          
        if abs(a-b)<=10**3<a+b-1:
            s+=rnag[10**3]-rnag[abs(a-b)]
            if abs(a-b)<a<=10**3:
                s-=1
            if abs(a-b)<b<=10**3:
                s-=1
print(s//3)

Submission status: Accepted

Solution code:
import bisect
inf = 10**15
mod = 10**9+7
n = int(input())
l = list(map(int, input().split()))
l.sort()
ans=0
for i in range(n-2):
    a = l[i]
    for j in range(i+1, n-1):
        b = l[j]
        indc = bisect.bisect_left(l,a+b)
        ans+=(indc-j-1)
print(ans)

Submission status: Accepted

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):
    k = bisect.bisect_left(l, l[i] + l[j])
    if k > j:
      ans += k - j - 1
    else:
      pass


print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

ans = 0
for i in range(N):
  for j in range(i+1, N):
    idx = bisect.bisect_left(L[j+1:], L[i]+L[j])
    ans += idx 
print(ans)

Submission status: Accepted

Solution code:
'''@masayoshi361   Qiita　　三重ループはTLE。要素固定⇒二分探索
こういういくつも要素が動く系の数え上げはいくつかを固定してあげると
うまくいくことがあります。今回、三角形に使う棒の長さをa<=b<=cとして、
b, cを固定すると、a>c-bとなるaの数え上げに帰着します。単調性から、
二分探索でlognで求められるので、全体ではO(N^2logN)です。
'''
from bisect import bisect_right
N = int(input())
L = list(map(int, input().split()))
L.sort()#昇順ソート、小さいものから大きいものへ
#bisectを使う前にソートが必要
ans = 0
for i in range(N):
    for j in range(i):#jはi未満
        m = L[i]-L[j]#上記c-aを計算
        k = bisect_right(L, m)#二分探索
        #aに相当するkは、上記の通り、mよりも大きい(つまり、右側)
        #同じものがあったら右側
        n = max(0, j-k)#j-kの区間の数は大丈夫
        ans+=n
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
import bisect
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def lcm(x, y) : return (x * y) // math.gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

N = I()
L = LI()

L.sort()

ans = 0
for i in range(N):
    for j in range(i+1, N):
        c = bisect.bisect_left(L, L[i]+L[j])

        ans += max(0, c - (j+1))

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    N = int(input())
    L = list(map(int, input().split()))
    L.sort()
    ans = 0
    for i in range(N):
        right = i + 2
        for left in range(i+1, N):
            while right < N and L[right] < L[i] + L[left]:
                right += 1
            ans += right - (left+1)
            if left == right:right += 1
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
'''@masayoshi361   Qiita　　三重ループはTLE。要素固定⇒二分探索
こういういくつも要素が動く系の数え上げはいくつかを固定してあげると
うまくいくことがあります。今回、三角形に使う棒の長さをa<=b<=cとして、
b, cを固定すると、a>c-bとなるaの数え上げに帰着します。単調性から、
二分探索でlognで求められるので、全体ではO(N^2logN)です。
'''
from bisect import bisect_right
N = int(input())
L = list(map(int, input().split()))
L.sort()#昇順ソート、小さいものから大きいものへ
ans = 0
for i in range(N):
    for j in range(i):#jはi未満
        m = L[i]-L[j]#上記c-aを計算
        k = bisect_right(L, m)#二分探索
        #aに相当するkは、mよりも大きい(つまり、右側)
        n = max(0, j-k)#j-kの区間の数は大丈夫
        ans+=n
print(ans)

Submission status: Accepted

Solution code:
import bisect

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

ans = 0
for m in range(N):
    for s in range(m):
        #このfor文の時点で、時点でs<mを満たす。
        # L[m] <= L[l] < L[s] + L[m]
        # 使用している辺は使えず、sortしてあるので、m<lという条件が加わる。
        # m<lの時点で、L[m] <= L[l]は満たすので、m<l とL[l] < L[s] + L[m]で考える。
        ans += bisect.bisect_left(L,L[s]+L[m]) - (m+1)
        
print(ans)

Submission status: Accepted

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):
        idx = bisect.bisect_left(l,l[i]+l[j])
        ans += idx-1-j
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

res = 0
for i in range(n):
    for k in range(i+1, n):
        res += bisect_left(l, l[i]+l[k]) - (k + 1)
print(res)

Submission status: Accepted

Solution code:
from bisect import*
n, *l = map(int, open(0).read().split())
l.sort();c=0
for i in range(n):
  for j in range(i+1, n):
    d = bisect_left(l, l[i] + l[j])
    c += max(0, d-j-1)
print(c)

Submission status: Accepted

Solution code:
from bisect import bisect_left
 
N = int(input())
L = sorted(list(map(int, input().split())))
 
ans = 0
for i in range(N):
    for j in range(i + 1, N):
        a = L[i]
        b = L[j]
        idx = bisect_left(L, a + b)
        ans += idx - 1 - j
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        a = L[i]
        b = L[j]
        idx = bisect_left(L, a + b)
        ans += idx - 1 - j
print(ans)

Submission status: Accepted

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

c=0

import bisect

for i in range(n-2):
    for j in range(i+1, n-1):
        c += bisect.bisect_left(l, l[i]+l[j]) - j - 1
print(c)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import defaultdict, deque, Counter
import sys
from bisect import bisect_left
import heapq
import math

sys.setrecursionlimit(1000000000)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

n = int(stdin.readline().rstrip())
l = list(map(int, stdin.readline().rstrip().split()))
#A, B, C = map(int, stdin.readline().rstrip().split())
#S = [list(stdin.buffer.readline().decode().rstrip()) for _ in range(h)]

l.sort()
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: Accepted

Solution code:
import bisect
n = int(input())
l = sorted(list(map(int,input().split())))
cou =0
for i in range(0,n-2):
  for j in range(i+1,n-1):
    #iがaの長さ、jがbの長さ
    m = l[i]
    u = l[j]
    c =bisect.bisect_left(l,m+u)
    if c>j+1:
      cou += c-j-1
print(cou)

Submission status: Accepted

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

l.sort()

ans = 0
for a in range(n):
    for b in range(a + 1, n):
        c = bisect.bisect_left(l, l[a] + l[b])
        if b < c:
            ans += c - (b + 1)

print(ans)

Submission status: Accepted

Solution code:
import sys
import bisect
input = sys.stdin.readline
 
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):
        index = bisect.bisect_left(L, L[i] + L[j])
        n = index - j - 1
        ans += n
 
print(ans)

Submission status: Accepted

Solution code:
import bisect


def main():
    N = int(input())
    L = list(map(int, input().split(' ')))
    L.sort()
    cnt = 0
    for i in range(N - 2):
        for j in range(i + 1, N - 1):
            index = bisect.bisect_left(L, L[i] + L[j])
            cnt += max([0, index - j - 1])
    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import bisect
def main():
    N = int(input())
    L = list(map(int, input().split()))
    L.sort()
    MAX = 2000
    C = [0] * MAX
    S = [0] * (MAX+1)
    for val in L:
        C[val] += 1
    for i in range(MAX):
        S[i+1] = C[i] + S[i]
    ans = 0
    for i in range(N):
        for j in range(N):
            if i == j:continue
            left = abs(L[i]-L[j])+1
            right = L[i]+L[j]
            ans += S[right]-S[left]
            if left <= L[i] < right:ans -= 1
            if left <= L[j] < right:ans -= 1
    print(ans//6)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect


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


l.sort()
c = 0
for i in range(n)[::-1]:
    for j in range(i)[::-1]:
        d = l[i] - l[j]
        idx = bisect.bisect_right(l,d)
        c += max(0,j-idx)
print(c)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import bisect
def main():
    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):
            idx = bisect.bisect_left(L, L[i]+L[j], j+1, N)
            ans += idx-j-1
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect

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

res = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        index = bisect.bisect_left(L, L[i] + L[j])
        n = max(0, (index - 1) - j)
        res += n

print(res)

Submission status: Accepted

Solution code:
import bisect

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

res = 0
for i in reversed(range(1, N)):
    for j in reversed(range(i)):
        index = bisect.bisect_left(L, L[i] + L[j])
        n = N - index
        res += (N - 1 - i) - n

print(res)

Submission status: Accepted

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

Edges=sorted(Edges)
cnt =0
# for i in c:
#     e1=(i[1] + i[2])
#     e2=(i[0] + i[2])
#     e3=(i[0] + i[1])

#     if i[0] < e1 and i[1] < e2 and i[2] < e3:
#         cnt+=1


import bisect

for a in range(N-2):
    for b in range(a+1,N-1):
        ab = Edges[a] + Edges[b]

        idx = bisect.bisect_left(Edges,ab)

        cnt += max(0,idx-b-1)


print(cnt)

Submission status: Accepted

Solution code:
import bisect

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

count  =0
L.sort()
for i in range(0, N - 1):
  for j in range(i + 1, N):
    index = bisect.bisect_left(L, L[i] + L[j]) 
    count += max(0, index - j - 1)
print(count)

Submission status: Accepted

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

for i in range(N-1,0,-1):
    l = 0
    r = i -1
    while(l< r):
        if (A[l] + A[r] >A[i]):
            count += (r-l)
            r -= 1
        else:
            l += 1
print(count)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc143/tasks/abc143_d

import bisect

N = int(input())
L_list = list(map(int, input().split()))
L_list = sorted(L_list)
count = 0

for a in range(N-2):
    for b in range(a + 1, N-1):
        c_min = L_list[b + 1]
        c_max = L_list[a] + L_list[b]
        c_max_idx = bisect.bisect_left(L_list, c_max)
        c_count = c_max_idx - (b + 1)
        count += c_count

print(count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
import collections
import itertools
import bisect
mod = 10 ** 9 + 7
N = int(input())
L = list(map(int, input().split()))
L = sorted(L)
count = 0
for i in range(len(L)):
    for j in range(i+1, len(L)):
        a = L[i]
        b = L[j]
        idx = insert_index = bisect.bisect_left(L, a+b)
        count += max(0, idx-j-1)


print(count)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
 
def main():
    num = 0
    _ = input()
    A = sorted(list(map(int, input().split())))
    for i in range(len(A)-1):
        for j in range(i+1, len(A)):
            a = A[i]
            b = A[j]
            thresh = a + b
            ok = j
            ng = len(A)
            idx = binary_search(A, ok, ng, thresh)
            num += idx - j
 
    print(num)
 
 
def binary_search(li, ok, ng, value):
    while abs(ok-ng) > 1:
        mid = (ok + ng) // 2
        if li[mid] < value:
            ok = mid
        else:
            ng = mid
 
    return ok
 
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect
n = int(input())
lst = list(map(int, input().split()))
lst.sort()

ans = 0

for i in range(n-2):
  for j in range(i+1, n-1):
    a = lst[i]
    b = lst[j]
    border = a + b
    dig = bisect.bisect_left(lst, border)
    ans += max(0, dig - j - 1)
    
print(ans)

Submission status: Accepted

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

for i in range(N-1,0,-1):
    l = 0
    r = i -1
    while(l< r):
        if (A[l] + A[r] >A[i]):
            count += (r-l)
            r -= 1
        else:
            l += 1
print(count)

Submission status: Accepted

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

def main():
    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):
            index = bisect_left(L,L[i]+L[j])
            ans += max(0,index-j-1)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def main():
    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):
            diff = L[j] - L[i]
            index = bisect_right(L[:i],diff)
            ans += i-index
            # print(i,j,ans)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
l = sorted(list(map(int,input().split())))
ans = 0
import bisect
for i in range(n):
    for j in range(i+1,n):
        a = l[i]+l[j]
        x = bisect.bisect_left(l,a)
        if x>j:
            ans += max(0,x-j-1)
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
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):
        a = l[i]
        b = l[j]
        ans += bisect_left(l, a + b) - j - 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
l_list = list(map(int,input().split()))
l_list.sort()
import bisect
count = 0
for i in range(1,n):
  for j in range(i+1,n):
    b = l_list[i]
    c = l_list[j]
    a_cand = l_list[:i]
    border = c-b
    count += len(a_cand) - bisect.bisect_right(a_cand,border)
print(count)

Submission status: Accepted

Solution code:
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):
        index = bisect.bisect_right(L, L[i] + L[j]-1)
        ans += index - j - 1

print(ans)

Submission status: Accepted

Solution code:
def main():
    import bisect
    n = int(input())
    l = sorted(list(map(int,input().split())))
    ans = 0
    for i in range(1,n-1):
        ll = l[0:i]
        lr = l[i+1:]
        c = l[i]
        for j in range(len(lr)):
            b = bisect.bisect_left(ll,lr[j]-c+1)
            ans += len(ll)-b
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect
N=int(input())
L=list(map(int,input().split()))
L.sort()
ans = 0
for a in range(N):
  for b in range(a+1,N):
    c=bisect.bisect_left(L, L[a]+L[b])#第一条件(終点)
    if b<c:#第2条件（始点）
      ans+=c-b-1     
print(ans)#bisectのインデックスより一個前なら小さい

Submission status: Accepted

Solution code:
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):
        ans += bisect.bisect_left(L, L[i] + L[j]) - (j+1)
print(ans)

Submission status: Accepted

Solution code:
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):
        res = L[i] + L[j]
        num = bisect.bisect_left(L, res) - (j+1)
        ans += num
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(len(l)-1, 1, -1):
  for j in range(i-1, 0, -1):
    if l[i]//2 >= l[j]:
      break
    ind = bisect.bisect_left(l, l[i]-l[j]+1)
    ans += j - ind
print(ans)

Submission status: Accepted

Solution code:
import bisect
 
n=int(input())
a=list(map(int,input().split()))
a=sorted(a)
ans=0
for i in range(n-2):
    for j in range(i+1,n-1):
        tmp=a[i]+a[j]
        index=bisect.bisect_left(a,tmp)
        ans+=index-j-1
print(ans)

Submission status: Accepted

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):
        b = L[i] + L[j]
        ans += bisect_left(L, b) - 1 - j 
print(ans)

Submission status: Accepted

Solution code:
import bisect

if __name__ == '__main__':
    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):
            ab = l[i] + l[j]
            ans += bisect.bisect_left(l, ab) - j - 1
    print(ans)

Submission status: Accepted

Solution code:
import bisect

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

ans=0
for i in range(n-2):
    for j in range(i+1,n-1):
        tmp=a[i]+a[j]
        index=bisect.bisect_left(a,tmp)
        ans+=index-j-1

print(ans)

Submission status: Accepted

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

from bisect import bisect_left

ans = 0
for i in range(1,N-1):
    for j in range(i+1,N):
        ans += (bisect_left(L,L[i]+L[j]))-j-1

#短い2本を固定して考える

print(ans)

Submission status: Accepted

Solution code:
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):
        right=bisect.bisect_left(l,l[i]+l[j])
        left=j+1
        ans += right -left

print(ans)

Submission status: Accepted

Solution code:
from copy import copy
from collections import deque
import bisect
N = int(input())
L = list(map(int, input().split()))
L.sort()
first = deque(L)
count = 0
for i in range(N-2):
    l = first.pop()
    second = copy(first)
    for j in range(1,N-i-1):
        m = second.pop()
        n = len(second) - bisect.bisect_right(second,l-m)
        if n > 0:
            count += n
        else:
            break
print(count)

Submission status: Accepted

Solution code:
import bisect

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

L.sort()
res = 0
for i in range(N):
    for j in range(i+1, N):
        query = L[i] + L[j]
        res += bisect.bisect_left(L, query) - j - 1

print(res)

Submission status: Accepted

Solution code:
import bisect
def main():
    N = int(input())
    L = sorted([int(_) for _ in input().split()])

    ret = 0
    for i in range(N):
        for j in range(i+1, N):
            x = bisect.bisect_left(L, L[i] + L[j])
            ret += x - j - 1
    print(ret)

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    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):
            ab = L[i] + L[j]
            idx = bisect.bisect_left(L, ab)
            ans += max(idx - j - 1, 0)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect
n=int(input())
l=list(map(int,input().split()))
l=sorted(l)
ans=0
for i in range(n-2):
  for k in range(i+1,n-1):
    ans+=bisect.bisect_left(l,l[i]+l[k])-k-1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
L = list(map(int, input().split()))
L.sort(reverse=True)
L_ = []
for i in range(N):
    L_ += [L[i]*(10**3) + (N-i-1)]
# length_list[m] m 以下の長さの辺の個数
length_list = [0] * (10**3 + 1)
for i in range(N):
    length_list[L[i]] += 1
for i in range(10**3):
    length_list[i+1] += length_list[i]

length_list_ = [0] * (2* 10**6 + 1)
for i in range(N):
    length_list_[L_[i]] += 1
for i in range(2* 10**6):
    length_list_[i+1] += length_list_[i]
    
ans = 0
for i in range(N):
    for j in range(i+1,N):
        ans += max(0, length_list_[L_[j]-1] - length_list[(L[i]-L[j])] )
print(ans)

Submission status: Accepted

Solution code:
import bisect

N = int(input())

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

A.sort()

ans = 0
for a in range(N-2):
    for b in range(a+1, N-1):
        ans += bisect.bisect_left(A, A[a]+A[b])-b-1

print(ans)

Submission status: Accepted

Solution code:
import itertools, bisect

import math
def naive_cmb(n, r):
    if r < 0 or r > n:
        return 0
    return (math.factorial(n) // math.factorial(r)) // math.factorial(n-r)

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

two_edge_sum = [sum(x) for x in list(itertools.combinations(L,2))]
two_edge_sum.sort()
ans = naive_cmb(N,3)

for l in L:
    ans -= bisect.bisect_right(two_edge_sum, l)

print(max(ans,0))

Submission status: Accepted

Solution code:
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
from bisect import bisect_left, bisect_right
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        ans = ans - j - 1 + bisect_left(a, abs(a[i] + a[j]))
print(ans)

Submission status: Accepted

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

l.sort()
l.append(10**9)
cnt=0
i=0
#print(l)

while i<n-2:
    j=i+1
    while j<n-1:
        LL=j+1
        RR=n-1
        #print("#",l[i],l[j],l[LL],l[RR])
        while LL<=RR:
            k=(LL+RR)//2
            if k==n:
                break
            #print(l)
            #print(i,j,LL,RR,k)
            #print(l[i]+l[j],l[k],l[k+1])
            if l[i]+l[j]>l[k] and l[i]+l[j]<=l[k+1]:
                cnt+=k-j
                break
            elif LL==RR:
                break
            elif l[i]+l[j]<=l[k]:
                RR=k
            elif l[i]+l[j]>l[k]:
                LL=k+1
            elif l[i]+l[j]<l[k] and k==j+1:
                break
        j+=1
    i+=1

print(cnt)

Submission status: Accepted

Solution code:
import bisect

n = int(input())
l = list(map(int, input().split()))
l.sort()
c = 0
for i in range(n - 2):
    for j in range(i + 1, n - 1):   
        c += bisect.bisect_left(l, l[i] + l[j]) - j - 1
print(c)

Submission status: Accepted

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

import bisect
L=sorted(L)
comb = 0
for a in range(N-2):
    for b in range(1+a,N-1):
        posIndex = bisect.bisect_left(L, L[a] + L[b])
        comb += posIndex - b - 1 if posIndex != 0 else 0
print(comb)

Submission status: Accepted

Solution code:
n=int(input())
#a,b=map(int,input().split())
l=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]

import bisect

l.sort()
ans=0
for i in range(n):
    for j in range(i+1,n):
        a=l[i]
        b=l[j]
        index=bisect.bisect_left(l,a+b)
        ans+=max(index-(j+1),0)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
#a,b=map(int,input().split())
l=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]

import bisect

l.sort()
ans=0
for i in range(n):
    for j in range(i+1,n):
        a=l[i]
        b=l[j]
        index=bisect.bisect_left(l,a+b)
        ans+=max(index-(j+1),0)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
li = list(map(int, input().split()))
li.sort(reverse=True)
count = 0

for i in range(n-2):
    for j in range(i+1, n-1):
        left = j
        right = n

        while right - left > 1:
            mid = (left + right)//2
            if li[i]-li[j] < li[mid]:
                left = mid
            else:
                right = mid
        count += left - j

print(count)

Submission status: Accepted

Solution code:
import bisect

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

L = sorted(L)

for c in reversed(range(2, N)):
	for b in reversed(range(1, c)):
		a = bisect.bisect_right(L, L[c]-L[b])
		if a<b:
			s += b-a
print(s)