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:
from itertools import combinations
from bisect import bisect_right

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

    L.sort()

    print(sum(bisect_right(L, L[i] + L[j] - 1, j + 1) - (j + 1) for i, j in combinations(range(N), 2)))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left

n = int(input())
l_ls = sorted(map(int, input().split()))

ans = 0

for i in range(n):
    for j in range(i+1, n):
        a, b = l_ls[i], l_ls[j]
        right = bisect_left(l_ls, a+b)
        ans += right-(j+1)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# https://takeg.hatenadiary.jp/entry/2019/11/22/212816

import bisect

def solve():
    N = int(input())
    Ls = list(map(int, input().split()))
    Ls.sort()

    # O(N^2 * logN)の全探索で解く
    ans = 0
    for a_i in range(N):
        for b_i in range(a_i+1, N):
            c_i = bisect.bisect_left(Ls, Ls[a_i]+Ls[b_i])
            if c_i > b_i:
                ans += c_i - b_i - 1
            else:
                pass

    print(ans)

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''


def sol(n,l):
    import bisect
    l.sort()
    ans = 0
    #print(l)
    for i in range(n-1):
        for j in range(i+1,n):
            ji = l[j]+l[i]
            ind = bisect.bisect_left(l,ji)
            #print(i,j,ind,ind-j-1)
            ans += ind-j-1
    return ans


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

        
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect

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

answer = 0

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

print(answer)

Submission status: Accepted

Solution code:
n=int(input())
# s=input()
# a,b=map(int,input().split())
# h=list(map(int,input().split()))
l=sorted(list(map(int,input().split())))

# mod=10**9+7
# n=20
# fact=[1]
# for i in range(n):
#     fact+=fact[-1]*(i+1)%mod,
# print(fact)
# print(l)
# ほんと？
from bisect import bisect_left,bisect_right
ans=0
for i in range(n):
    for j in range(i+1,n):
        a=l[i]
        b=l[j]
        
        # print(ll)
        # abs(a-b)<c<a+bをみたすcは何個？
        ans+=bisect_left(l,a+b)-j-1 # -bisect_right(ll,b-a)
print(ans)

Submission status: Accepted

Solution code:
from itertools import *
from bisect import *

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

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

Submission status: Accepted

Solution code:
# coding: utf-8
from bisect import bisect_left, bisect_right

n = int(input().rstrip())
bo = sorted([int(i) * -1 for i in input().rstrip().split(" ")])

ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        if j < int(i/2):
            break
        idx = bisect_left(bo, bo[i]-bo[j], j+1)
        ans += idx - j - 1

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
from bisect import bisect_left, bisect_right

n = int(input().rstrip())
bo = sorted([int(i) * -1 for i in input().rstrip().split(" ")])

def get_count(start:int, num:int):
    if bo[len(bo)-1] > num:
        return len(bo)-1
    if bo[start] <= num:
        return -1
    return get_count_sub(start, len(bo)-1, num)

def get_count_sub(min:int, max:int, target:int):
    if max - min <= 1:
        if bo[max] > target:
            return max
        else:
            return min

    mid = int((max+min)/2)
    if bo[mid] > target:
        return get_count_sub(mid, max, target)
    else:
        return get_count_sub(min, mid, target)

ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        if j < int(i/2):
            break
        idx = bisect_left(bo, bo[i]-bo[j], j+1)
        ans += idx - j - 1

print(ans)

Submission status: Accepted

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

l.sort()

ans = 0
for i in range(n-2):
    l1 = l[i]

    l3_ind = i+2
    for j in range(i+1,n):
        l2 = l[j]
        while(True):
            if(l3_ind == n):
                ans += l3_ind - j - 1
                break

            if(l[l3_ind] >= l1+l2):
                ans += l3_ind - j - 1
                break
            l3_ind += 1
            
print(ans)

Submission status: Accepted

Solution code:
import bisect
n = int(input())
dat = list(map(int, input().split()))
dat.sort(reverse=True)
dat = list(map(lambda x: -x, dat))
#print(dat)
res = 0
for a in range(n):
    #print("a={0}, [{1}]".format(dat[a],a))
    for b in range(a+1, n):
        #print("b={0}, [{1}]".format(dat[b],b))
        cind = bisect.bisect_left(dat, dat[a] - dat[b], b)
        cannum = cind - (b+1)
        cannum = 0 if cannum < 0 else cannum
        #print("cind", cind)
        #print("cannum", cannum)
        res += cannum
print(res)

Submission status: Accepted

Solution code:
import array
import bisect

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

L.sort()

A = array.array('i', L)

#print(L)
#print(A)

count = 0

for ia in range(2,N):
    for ib in range(1, ia):
        ic_max = ib-1
        c_min = A[ia]-A[ib]
        ic_min = bisect.bisect_right(A, c_min)
        #print('---------------------')
        #print(ia, ib, ic_max, ic_min)
        #print(A[ia], A[ib], A[ic_max], A[ic_min])
        c_count = ic_max - ic_min + 1
        if c_count > 0:
            count += c_count

print(count)

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import bisect
input = sys.stdin.readline
MOD = 10**9 + 7
INF = float('INF')

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

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

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  n  = int(input())
  Ls = list(map(int, input().strip().split())) + [2*10**3+1]
  Ls.sort()
  def bs(l, r, x):
    while r - l > 1:
      mid = (r+l)//2
      if Ls[mid] >= x:
        r = mid
      if Ls[mid] <  x:
        l = mid
    return r
  
  count = 0
  for i in range(n-2):
    for j in range(i+1, n-1):
      r = bs(j, len(Ls), Ls[i]+Ls[j])
      count += (r - 1  - j)
  print(count)
  
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left, bisect_right

n, *l = map(int, sys.stdin.read().split())
l.sort()
ans = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        # i: 1番目に長い棒　j: 2番目に長い棒
        # 3番目に長い棒の条件 -> jよりも短く a<b+cよりa-bより大きい
        cnt = (n - 1) - j - bisect_right(l, l[-(i+1)] - l[-(j+1)])
        if cnt > 0:
            ans += cnt
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
v = list(sorted(map(int, input().split())))
v.append(2000)
total = n*(n-1)*(n-2) / 6



def bs(left, s):
    right = n+1
    while left < right-1:
        m = (right+left)//2

        if v[m]>=s:
            right = m
        else:
            left = m
    return right


for i, x in enumerate(v[:-2]):
    for j, y in enumerate(v[i+1:-1]):
        k = bs(j, y+x)
        total -= (n-k)

print(int(total))

Submission status: Accepted

Solution code:
n = int(input())
v = list(sorted(map(int, input().split())))
v.append(2000)
total = n*(n-1)*(n-2) / 6



def bs(left, s):
    right = n+1
    while left < right-1:
        m = (right+left)//2

        if v[m]>=s:
            right = m
        else:
            left = m
    return right






for i, x in enumerate(v[:-2]):
    for j, y in enumerate(v[i+1:-1]):
        k = bs(j+1, y+x)
        total -= (n-k)

print(int(total))

Submission status: Accepted

Solution code:
n = int(input())
v = list(sorted(map(int, input().split())))
v.append(2000)
total = n*(n-1)*(n-2) / 6



def bs(left, s):
    right = n+1
    while left < right-1:
        m = (right+left)//2

        if v[m]>=s:
            right = m
        else:
            left = m
    return left+1






for i, x in enumerate(v[:-2]):
    for j, y in enumerate(v[i+1:-1]):
        k = bs(j+1, y+x)
        total -= (n-k)

print(int(total))

Submission status: Accepted

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

from bisect import bisect_left

cnt = 0
for i in range(0, N - 2):
    for j in range(i + 1, N - 1):
        t = L[i] + L[j]
        idx = bisect_left(L, t, j + 1, len(L))
        cnt += max(0, idx - j - 1)
print(cnt)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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, j+1)
    ans += max(0, idx-j-1)
print(ans)

Submission status: Accepted

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

from bisect import bisect_left 
cnt = 0
for i in range(0,N):
  for j in range(i+1,N):
    t = L[i]+L[j]
    idx = bisect_left(L,t)
    cnt += max(0,idx-j-1)
print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
L = sorted([int(l) for l in input().split()])
INF = 10**8
L.append(INF)
L.append(INF)

num = 0
for na in range(N-2):
    for nb in range(na+1, N - 1):
        r = N+1
        l = nb
        while r - l > 1:
            c = (l + r) // 2
            if L[c] < L[na] + L[nb]:
                l = c
            else:
                r = c
        num += l - nb

print(num)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	L = inputList()
	L.sort()
	#print(L)

	ans = 0
	for a in range(N):
		for b in range(a+1,N):
			A = L[a]
			B = L[b]
			tmp = A + B
			C_ind = bisect_left(L, tmp)

			if C_ind >= N:
				ans += N - b - 1
			else:
				ans += C_ind - b - 1

	print(ans)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# special thanks :
#  https://nagiss.hateblo.jp/entry/2019/07/01/185421
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import sys
import bisect

N = int(sys.stdin.readline())
L = list(map(int, sys.stdin.readline().split()))
L = sorted(L)

count = 0
for a_i in range(N-1):
    for b_i in range(a_i+1, N):
        max_c = bisect.bisect_left(L, L[a_i]+L[b_i])
        if max_c > b_i:
            count += max_c - b_i - 1
        
print(count)

Submission status: Accepted

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

ans = 0
for i in range(1,n-1):
  for j in range(i):
    if L[n-1] - L[i]-L[j] < 0:
      ans += (n-1) - (i+1) + 1
      continue
    elif L[i+1] - L[i]-L[j] >= 0:
      continue
    l = i+1
    r = n-1
    while abs(r-l) > 1:
      mid = (l+r)//2
      if L[i]+L[j] - L[mid]> 0:
        l = mid
      else:
        r= mid
    ans += l-(i+1)+ 1
print(ans)

Submission status: Accepted

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

count=0
l=sorted(L)
#print(l)
for i in range(N-2):
    for j in range(i+1,N-1):
        count+=bi.bisect_left(l,l[i]+l[j],j+1)-j-1
         
print(count)

Submission status: Accepted

Solution code:
import bisect

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

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

print(count)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect

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

ld={}
for i in range(n):
    ld.setdefault(i,ls[i])
#print(ld)

ans=0
for i in range(n-2):
    for j in range(i+1, n-1):
        k = bisect.bisect_left(ls, ld[i]+ld[j])
        #print(k)
        ans += k-j-1

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

L_sorted = sorted(L)

count = 0
for i in range(N):  # shortest stick
    for j in range(i+1, N):  # second shortest stick
        r = bisect_left(L_sorted, L_sorted[i] + L_sorted[j], j)
        count += r - j - 1

print(count)

Submission status: Accepted

Solution code:

from bisect import bisect_right

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

L_sorted = sorted(L)

count = 0
for i in range(N):  # longest stick
    for j in reversed(range(i)):  # second longest stick
        r = bisect_right(L_sorted, L_sorted[i] - L_sorted[j])
        if j <= r:
            break
        else:
            count += j - r

print(count)

Submission status: Accepted

Solution code:
from bisect import bisect_right

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

L_sorted = sorted(L)

count = 0
for i in range(N):  # longest stick
    for j in range(i):  # second longest stick
        r = bisect_right(L_sorted, L_sorted[i] - L_sorted[j])
        count += max(0, j - r)

print(count)

Submission status: Accepted

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

  
ans=0
for i in range(len(ll)-1):
  for j  in range(i+1,len(ll)):
    a,b=ll[i],ll[j]
    ans+=bisect.bisect_left(ll,a+b)-(j+1)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from bisect import bisect_left,bisect_right
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):
        bc=l[i]+l[j]
        idx=bisect_left(l,bc)
        ans+=idx-j-1
print(ans)

Submission status: Accepted

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

for a in range(N - 1, 0, -1):
    b = 0
    c = a - 1
    while (b < c):
        if L[a] < L[b] + L[c]:
            cnt += c - b
            c -= 1
        else:
            b += 1

print(cnt)

Submission status: Accepted

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

L_array.sort()

# print(L_array)
ans = 0
for i in range(N):
    for j in range(i+1,N):
        max_len = L_array[i] + L_array[j] - 0.1
        max_index = bisect.bisect_left(L_array,max_len) - 1
        # print(i,j,max_len,max_index)
        if j < max_index:
            ans += (max_index - j)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
sticks = list (map (int, input().strip().split()))
sticks.sort()
ans = 0
for a_idx in range(n - 1, 0, -1):
    b_idx = a_idx - 1
    c_idx = 0
    while c_idx < b_idx:
        if sticks[a_idx] < sticks[b_idx] + sticks[c_idx]:
            ans += b_idx - c_idx
            b_idx -= 1
        else:
            c_idx += 1
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right

def main():
    N = int(input())
    L = list(map(int, input().split()))
    sort_L = sorted(L)
    ans = 0
    for i in range(N-2):
        for j in range(i,N-1):
            if i == j:
                continue
            ok = j
            ng = N
            tmp = sort_L[i] + sort_L[j]
            while abs(ok - ng) > 1:
                mid = (ok + ng) // 2
                if sort_L[mid] < tmp:
                    ok = mid
                else:
                    ng = mid

            ans += ok - j

    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
L = list(map(int,input().split()))
L.sort()
import bisect
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:
from bisect import bisect_left
n=int(input())
L=sorted((map(int,input().split())))
t=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[i]+L[j]>L[c]:
				l=c
			else:
				r=c
		t+=l-j
print(t)

Submission status: Accepted

Solution code:
import bisect
N = int(input())
L = sorted([int(x) for x in input().split()])
cnt = 0
#print(L)
for i in range(N-2):
    for j in range(i+1, N-1):
        #print(i, j)
        #print(bisect.bisect_left(L, L[i]+L[j]))
        cnt +=  bisect.bisect_left(L, L[i]+L[j]) - (j+1)
print(cnt)

Submission status: Accepted

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

li.sort()
ans = 0

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


sys.setrecursionlimit(1000000)
MOD = int(1e09) + 7
INF = int(1e30)


def main():
    # sys.stdin = open("Sample.txt")
    N = Scanner.int()
    L = Scanner.map_int()
    L.sort()

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


if __name__ == "__main__":
    main()

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):
        #最初にa+b以上になるインデックスを二分探索で求める
        k = bisect.bisect_left(l, l[i]+l[j])
        res += max(k-(j+1),0)
print(res)

Submission status: Accepted

Solution code:
import bisect

def solve():
    N = int(input())
    Ls = list(map(int, input().split()))
    Ls.sort()
    
    ans = 0
    for a_i in range(N):
        for b_i in range(a_i+1, N):
            c_i = bisect.bisect_left(Ls, Ls[a_i] + Ls[b_i])
            if c_i > b_i:
                ans += c_i - b_i -1
            else:
                pass
    print(ans)

solve()

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

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left

read=sys.stdin.buffer.readline

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

L.sort()

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

print(ans)

Submission status: Accepted

Solution code:
import bisect

n = int(input())
l = sorted(list(map(int,input().split())))
count = 0
for i in range(2,n):
	for j in range(1,i):
		count += max(j - bisect.bisect_right(l, l[i] - l[j]) , 0)

print(count)

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

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

print(cnt)

Submission status: Accepted

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

for i in range(N):
    r = i+1
    for j in range(i):
        t = A[i] + A[j]
        while r < N and A[r] < t:
            r += 1
        l = i+1
        ans += max(0, r-l)
print(ans)

Submission status: Accepted

Solution code:
import math
from bisect import bisect_right
from bisect import bisect_left

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):
        lg = L[i] + L[j]
        st = L[j] - L[i]
        if lg > L[j+1] and st < L[n-1]:
            if lg > L[n-1]:
                m1 = n - (j+1)
            else:
                m1 = bisect_left(L[j+1:],lg)
            c += max(0,m1)
print (c)

Submission status: Accepted

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


        #print(i,j,ok,ng)

        ans += ok - j


print(ans)

Submission status: Accepted

Solution code:
import bisect

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

'''
リストをソートし、a, b <= cとなるようにa, bを取り出せば、
a < b + c, b < c + a という条件は満たすので、
a, bを取り出したとき、c < a + b を満たすcを二分探索で探す
'''

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:
from bisect import bisect_left

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

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

Submission status: Accepted

Solution code:
from bisect import bisect_left

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_left(L, L[i]+L[j]) - (j + 1)

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

def main():
    N=int(input())
    L=list(map(int,input().split()))
    long=[0 for i in range(0,1001)]
    for i in range(0,N):
        long[L[i]]+=1
    netlong=[]
    for i in range(1,1001):
        if long[i]>=1:
            netlong.append(i)
    X=list(accumulate(long))
    subans=[0 for i in range(0,2001)]
    ans=0
    for i in range(0,len(netlong)):
        a=netlong[i]
        for j in range(netlong[i]+1,2*netlong[i]-1):
            ans+=subans[j]*long[a]
        ans=ans+X[a-1]*long[a]*(long[a]-1)//2+long[a]*(long[a]-1)*(long[a]-2)//6
        for j in range(0,i):
            subans[a+netlong[j]]+=long[a]*long[netlong[j]]
        subans[2*a]+=long[a]*(long[a]-1)//2
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

#a<=b<=c とする
#a,b 固定
for i in range(N):
  for j in range(i+1,N):
    a,b = L[i],L[j]
    k = bisect.bisect_left(L,a+b)
    count += k-j-1
 
print(count)

Submission status: Accepted

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

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

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):
    a=L[i]
    for j in range(i+1, N):
        b=L[j]
        ans+=bisect.bisect_left(L, a+b)-(j+1)
print(ans)