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 bisect
n = int(input())
l = sorted(list(map(int, input().split())))
s = 0
for i in range(0,n-2):
  a = l[i]
  for j in range(i+1,n-1):
    b = l[j]
    s += bisect.bisect_left(l,a+b)-j-1
print(s)

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

print(ans)

Submission status: Accepted

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


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

    ans = 0
    for i in range(N-1, -1, -1):
        a = L[i]
        for j in range(i-1, -1, -1):
            b = L[j]
            ci = bisect.bisect_right(L, a-b, lo=0, hi=j)
            ans += j - ci
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ck = [0]*(N-2)
ans = 0
for i in range(N-2):
  j = i + 1
  k = N - 1
  while j < k:
    if L[i]-L[j]-L[k] < 0:
      ans += k-j
      j += 1 
    else:
      k -=1
  
print(ans)

Submission status: Accepted

Solution code:
import bisect

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

cnt = 0
for i in range(n-1):
    for j in range(i+1,n):
        up = l[j] + l[i]
        #l[k] = up となるようなkのうち最小のものを見つけろ
        k = bisect.bisect_left(l, up)
        cnt += k - j - 1
print(cnt)

Submission status: Accepted

Solution code:
from bisect import bisect
N = int(input())
L = sorted([int(_) for _ in input().split()])
ans = 0
for a in range(N - 2):
    for b in range(a + 1, N - 1):
        #print(bisect(L,L[a]+L[b]-1)-b-1)
        ans += bisect(L, L[a] + L[b] - 1) - b - 1
print(ans)

Submission status: Accepted

Solution code:
import bisect
import copy

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

cout = 0
m,k = 0,0

for i in range(n-2):
	o = list1.pop(0)
	for j in range(n-i-1):
		p = list1[j]

		a = abs(o-p) +1
		b = o+p -1 #<= ではなく<条件に揃える

		d = bisect.bisect_right(list1[j+1:],b)
		
		cout += d

print(cout)

Submission status: Accepted

Solution code:
from collections import Counter
from operator import add, mul
from functools import reduce
import bisect


def nCr(n, r):
    r = min(r, n - r)
    num = reduce(mul, range(n, n - r, -1), 1)
    den = reduce(mul, range(1, r + 1), 1)
    return num // den


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

Submission status: Accepted

Solution code:
from bisect import*;N,*L=map(int,open(0).read().split());L.sort();print(sum(j-bisect(L,L[i]-L[j],0,j)for i in range(N)for j in range(i)))

Submission status: Accepted

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

Submission status: Accepted

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


ans = 0
for i in range(N - 1 , 1, -1):
    for j in range(i - 1 , 0 , -1):
        #work = l[:j]
        x = l[i] - l[j]
        #idx = bisect.bisect_right(work, x)
        idx = bisect.bisect_right(l, x)
        ans += max(j - idx , 0)
print(ans)

Submission status: Accepted

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

ls = sorted(ll)
count = 0
for i in range(n-1):
  for j in range(i+1,n-1):
    x = bisect_left(ls,ls[i]+ls[j])
    count += x-j-1
    
print(count)

Submission status: Accepted

Solution code:
def slove():
    import sys
    import collections
    import bisect
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    l = list(map(int, input().rstrip('\n').split()))
    l.sort()
    cnt = 0
    d = collections.defaultdict(int)
    for i in range(n-2):
        for j in range(i+1, n-1):
            ma = l[i] + l[j]
            p = bisect.bisect_left(l, ma)
            if j < p:
                cnt += p - j - 1
    print(cnt)


if __name__ == '__main__':
    slove()

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

print(ans)

Submission status: Accepted

Solution code:
# D

import itertools
n = int(input())
l = list(map(int, input().split()))
l.sort()
 
from bisect import bisect_left
ans = 0

for i, j in itertools.combinations(range(len(l)),2):
    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


if __name__ == '__main__':
    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:

N=int(input())
L=[int(i) for i in input().split()]
L=sorted(L)
ans=0
import bisect

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect

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

ans = 0

#a<b+c, a>b-c, a>c-b
for a in range(n-2):
	for b in range(a+1,n-1):
		index = bisect.bisect_left(l,l[a]+l[b])
		ans += index - (b+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):
    idx = bisect.bisect_left(L, L[i] + L[j]) - 1
    ans += idx - j

print(ans)

Submission status: Accepted

Solution code:
def findnumberofTriangles(arr): 
  
    # Sort array and initialize count as 0 
    n = len(arr) 
    arr.sort() 
    count = 0
  
    # Fix the first element. We need to run till n-3 as 
    # the other two elements are selected from arr[i+1...n-1] 
    for i in range(0,n-2): 
  
        # Initialize index of the rightmost third element 
        k = i + 2
  
        # Fix the second element 
        for j in range(i+1,n): 
  
            # Find the rightmost element which is smaller 
            # than the sum of two fixed elements 
            # The important thing to note here is, we use 
            # the previous value of k. If value of arr[i] + 
            # arr[j-1] was greater than arr[k], then arr[i] + 
            # arr[j] must be greater than k, because the array 
            # is sorted. 
            while (k < n and arr[i] + arr[j] > arr[k]): 
                k += 1
  
            # Total number of possible triangles that can be 
            # formed with the two fixed elements is k - j - 1. 
            # The two fixed elements are arr[i] and arr[j]. All 
            # elements between arr[j+1] to arr[k-1] can form a 
            # triangle with arr[i] and arr[j]. One is subtracted 
            # from k because k is incremented one extra in above 
            # while loop. k will always be greater than j. If j 
            # becomes equal to k, then above loop will increment k, 
            # because arr[k] + arr[i] is always greater than arr[k] 
            if(k>j): 
                count += k - j - 1
  
    return count
n = int(input())
l = [int(x) for x in input().split()]
print(findnumberofTriangles(l))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

import bisect

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

L = sorted(L)

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

print(ans)

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]
        b = l[j]
        ans += bisect.bisect_left(l,a + b) - j - 1

print(ans)

Submission status: Accepted

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

score = 0

for i in range (N-2):
    for j in range (i+1, N-1):
        index = bisect.bisect_left(list, list[i] + list[j]) - j - 1
        score += index

print (score)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect
import sys
input = sys.stdin.readline
N = int(input())
list = list(map(int, input().split()))
list.sort()

score = 0

for i in range (N-2):
    for j in range (i+1, N-1):
        index = bisect.bisect_left(list, list[i] + list[j]) - j - 1
        score += index

print (score)

Submission status: Accepted

Solution code:
import bisect
N = int(input())
L_list =  sorted(list(map(int,input().split())))
#print(L_list)
result =0

for i in range(N):
    for j in range(i+1,N):
        a = L_list[i] + L_list[j]
        idx = bisect.bisect_left(L_list,a)
        result += max(0,idx-j-1)
print(result)

Submission status: Accepted

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

from bisect import bisect_left
for i in range(N):
    for j in range(i+1, N):
        ab = L[i] + L[j]
        index = bisect_left(L, ab)
        num = index - j - 1
        ans += max(0, num)

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left # 左から何番目に入るかを二分探索（O(logN)）で返す
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(N):
    L1 = L[i]
    for j in range(i+1, N):
        L2 = L[j]
        sumL = L1 + L2
        k = bisect_left(L, sumL)
        ans += max(0, k-j-1) # (k-1)-(j+1)+1

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

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

L.sort()
result = 0
for i in range(N - 2):
  a = L[i]
  for j in range(i + 1, N - 1):
    b = L[j]
    result += bisect_left(L, a + b) - j - 1
print(result)

Submission status: Accepted

Solution code:
import bisect

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

Llist.sort()

count = 0

for i in range(n-2):
    p = Llist[i]
    for j in range(i+1,n-1):
        q = Llist[j]
        k = bisect.bisect_left(Llist, p+q)
        count += (k-j-1)

print(count)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))
 
n = inp()
a = inpl()
ans = 0
a.sort()
for i in range(n-2):
    for j in range(i+1,n-1):
        tmp = a[i] + a[j] - 1
        tt = bisect.bisect_right(a[j+1:],tmp)
        if tt > 0 :
            ans += tt
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
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 - 1):
        ans += max(bisect.bisect_right(L, L[i] + L[j] - 1) - j - 1, 0)
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):
        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())
ll=list(map(int,input().split()))
ll.sort()
ans=0
for i in range(N):
    for j in range(i+1,N):
        if j==i+1:
            delta=bisect_left(ll,ll[i]+ll[i+1],lo=i+1)-i-2
            if delta>0:
                ans+=delta
            in_b=delta+i+1+1
        else:
            if in_b!=N:
                delta=bisect_left(ll,ll[i]+ll[j],lo=in_b)-j-1
            else:
                delta=N-j-1
            if delta>0:
                ans+=delta
            in_b=delta+j+1
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
from bisect import bisect
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i, j in combinations(range(1,N), 2):
    # a <= b <= c
    b, c = L[i], L[j]
    k = bisect(L, c-b)
    ans += max(0, i-k)

print(ans)

Submission status: Accepted

Solution code:
import bisect
import time

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

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

    print(ans)


if __name__ == "__main__":
    #start = time.time()
    main()
    #elapsed_time = time.time() - start
    #print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

Submission status: Accepted

Solution code:
import bisect


def main():
    N = int(input())
    edges = [int(i) for i in input().split()]
    edges.sort()
    ans = 0
    for a in range(N - 2):
        for b in range(a + 1, N - 1):
            ans += bisect.bisect_left(edges, edges[a] + edges[b])-b-1

    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

from bisect import bisect_left
for k in range(N-2):
    for j in range(k+1, N-1):
        ans += bisect_left(L[j+1:], L[k]+L[j])
 
 
print(ans)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect, bisect_left

input = sys.stdin.readline
N = int(input())
L = sorted([int(x) for x in input().split()])
c = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        f = bisect_left(L, L[i] + L[j])
        c += f - j - 1
print(c)

Submission status: Accepted

Solution code:
import sys
from itertools import combinations
import bisect
import math
n = int(input())
l_ls = [int(i) for i in sys.stdin.readline().split()]
l_ls.sort()
cnt = 0
for a, b in combinations(l_ls, 2):
    _sum = a + b
    ind = bisect.bisect_left(l_ls, _sum)
    cnt += n - ind
print(int(math.factorial(n) // math.factorial(3) // math.factorial(n-3)) - cnt)

Submission status: Accepted

Solution code:
from bisect import bisect_left
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+1, N):
        l = L[j] - L[i]
        r = L[j] + L[i]

        il = bisect_right(L, l, j)
        ir = bisect_left(L, r, j)

        if il == N-1:
            break

        ans += ir - il - 1

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect

n = int(input())
l = [int(i) for i in input().split()]

l.sort(reverse=True)
ans = 0

l = list(map(lambda x: x * (-1), l))

for i in range(n-2):
    for j in range(i+1,n-1):
        need = l[i] - l[j] - 1
        idx = bisect.bisect_right(l,need)
        #print(i,j,idx,need,ans)
        ans += max(0,idx-j-1)
        
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
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):
        insert_index = bisect.bisect_left(l,l[i]+l[j])
        ans+=(insert_index-j-1)
        
print(ans)

Submission status: Accepted

Solution code:
#from collections import Counter

#import numpy as np

input = raw_input
n = int(input())
#nums = np.zeros(2001, dtype=int)
nums = [0] * 2001
#nums = np.zeros(2001, dtype=int)

ls = map(int, input().split(" "))
#ls = Counter(map(int, ls))
#vals = ls.keys()
ls = sorted(ls)
for l in ls:
    #print(l)
    nums[l] += 1

set_vals = [val for val in range(2001) if nums[val] >= 1]
#print(vals)

#cumsum = np.cumsum(nums)

#print(set_vals)
len_set = len(set_vals)
out = 0
for i in range(len_set):
    val1 = set_vals[i]
    num_i = nums[val1]
    if num_i >= 3:
        out += (num_i * (num_i-1) * (num_i-2) // 6)
    
    if num_i >= 2:
        val2 = set_vals[i]
        for j in range(i+1, len_set):
            val3 = set_vals[j]
            num_h = nums[val3]
            if 2 * val1 <= val3:
                break

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

    for j in range(i+1, len_set):
        val2 = set_vals[j]
        num_j = nums[val2]

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

        for h in range(j+1, len_set):
            val3 = set_vals[h]
            #print(val1, val2, val3)
            num_h = nums[val3]
            if val1 + val2 <= val3:
                break

            #print("num", num_i, num_j, num_h)
            out += (num_i * num_j * num_h)

print(out)

Submission status: Accepted

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

import bisect

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

    L = sorted(L)

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

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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


print(sum)

Submission status: Accepted

Solution code:
import bisect

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

Submission status: Accepted

Solution code:
import bisect
N = int(input())
lst = list(map(int, input().split()))
lst.sort()
total = 0
for i in range(N-1):
    for j in range(i+1, N-1):
        x = bisect.bisect_left(lst, lst[i]+lst[j])
        total += x-j-1
print(total)

Submission status: Accepted

Solution code:
import bisect

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

score = 0

for i in range (N-2):
    for j in range (i+1, N-1):
        index = bisect.bisect_left(list, list[i] + list[j]) - j - 1
        score += index

print (score)

Submission status: Accepted

Solution code:
n = int(input())
l_list = list(map(int, input().split()))
l_list.sort()
count = [0 for i in range(2000)]
cum = [0 for i in range(2000)]
for l in l_list:
  count[l] += 1
for i in range(1, 2000):
  cum[i] = cum[i - 1] + count[i]

ans = 0
cnt = 0
for i in range(n - 2):
  for j in range(i + 1, n - 1):
    ans += cum[l_list[i] + l_list[j] - 1] - j - 1
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right
 
n = int(input())
a = sorted(map(int, input().split()))
print(sum(j - bisect_right(a, a[i] - a[j], 0, j)
          for i in range(2, n) for j in range(1, i)))

Submission status: Accepted

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

dp=[0]*(N+1)
ans=0
for i in range(3,N+1):
  r=i-2
  l=0
  c=0
  while r>l:
    if L[r]+L[l]>L[i-1]:
      c+=r-l
      r-=1
    else:
      l+=1
  dp[i]=dp[i-1]+c

print(dp[-1])

Submission status: Accepted

Solution code:
from bisect import bisect_left

n = int(input())
a = sorted(map(int, input().split()))
print(sum(bisect_left(a, a[i] + a[j], i + 1) - i - 1
          for i in range(1, n - 1) for j in range(i)))

Submission status: Accepted

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

def aaa(arr): 
    n = len(arr) 
    arr.sort() 
    count = 0
    for i in range(0,n-2): 
        k = i + 2
        for j in range(i+1,n): 
            while (k < n and arr[i] + arr[j] > arr[k]): 
                k += 1
            if(k>j): 
                count += k - j - 1
  
    return count 

print(aaa(L))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
l = sorted([int(i) for i in input().split()])
ans = 0
for i in range(1,n-1):
    tmp=0
    for j in range(i+1,n):
        if l[j] - l[i] >= l[i-1]:
            break
        else:
            for k in range(tmp,i):
                if l[tmp] > l[j]-l[i]:
                    ans += i-tmp
                    break
                elif l[k] > l[j]-l[i]:
                    tmp = k
                    ans += i-tmp
                    break
print(ans)

Submission status: Accepted

Solution code:
def CountTriangles(A):
    n = len(A);

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


if __name__ == '__main__':
    n = int(input())
    A = list(map(int,input().split()))

    CountTriangles(A);

Submission status: Accepted

Solution code:
from fractions import gcd
from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


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

    cnt = [n] * 3001
    l2 = sorted(l)
    t = 1
    for i in range(n):
        cnt[l2[i]] -= t
        t+=1
    for i in range(1,3001):
        if cnt[i] > cnt[i-1]:
            cnt[i] = cnt[i-1]


    ans = 0
    for i in range(n):
        a = l2[i]
        for j in range(i + 1, n):
            b = l2[j]
            t = bisect_left(l2, a + b)
            ans += (t - (j+1))
    print(ans)


        
    



    
            
    

    

    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
L = [int(i) for i in input().split()]
L.sort()
M = [0 for i in range(2*10**3+1)]
C = [0 for i in range(2*10**3+1)]
L_num = [1]
cnt = 1
for i in range(N-1):
    if L[i+1] == L[i]:
        cnt += 1
    else:
        cnt = 1
    L_num.append(cnt)
for i in range(N):
    M[L[i]] += 1
for i in range(1, len(M)):
    C[i] = C[i-1] + M[i]
cnt = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        a = L[i]
        b = L[j]
        cnt += C[a+b-1] - C[b-1] - L_num[j]
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-1,1,-1):
  for j in range(i-1,0,-1):
    L_ = L[:j]
    ans += j-bisect.bisect_right(L_,L[i]-L[j])
    
print(ans)

Submission status: Accepted

Solution code:
def A():
    temp = [int(i) for i in input().split()]
    print(max(0, temp[0]-2*temp[1]))

def B():
    N = int(input())
    T = [int(i) for i in input().split()]
    s = 0
    for i in range(N):
        for j in range(i):
            s += T[i]*T[j]
    print(s)

def C():
    N = int(input())
    S = input()
    if N == 1:
        print(1)
    else:
        ans = 1
        cur_c = S[0]
        for c in S:
            if c != cur_c:
                ans += 1
                cur_c = c
        
        print(ans)

from bisect import bisect_left, bisect_right
from itertools import combinations 

def D():
    N = int(input())
    L = sorted([int(i) for i in input().split()])
    count = 0
    for i in range(N):
        s = 0
        e = i-1
        while s<e:
            if L[i] < L[s]+L[e]:
                count += e-s
                e -= 1
            else:
                s += 1

    # dp_sum = [[0 for i in range(N)] for j in range(N)]
    # count = 0
    # for i in range(N):
    #     for j in range(i):
    #         print(L, L[i]+L[j])
    #         print(bisect_left(L, L[i]+L[j])-2, count)
    #         check_idx = bisect_left(L, L[i]+L[j])
    # count = 0
    # for i in range(N):
    #     for j in range(i):
    #         for k in range(j):
    #             if L[k] < L[i]+L[j] and L[j] < L[i]+L[k] and L[i] < L[j]+L[k]:
    #                 count += 1

    print(count)

D()

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N = int(input())
l = list(map(int, input().split()))
l.sort()

cnt = 0
pre_a = -1
for i in range(N-1,1,-1):
    tmp = 0
    a = l[i]
    lm = a//2
    pre_k = 0
    for j in range(i-1,0,-1):
        b = l[j]
        if b<=lm:
            continue
        a_b = a+b
        for k in range(pre_k,j):
            c = l[k]
            if (b+c>a):
                tmp += j-k
                pre_k = k
                break
    cnt += tmp
print(cnt)

Submission status: Accepted

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

L.sort()
larger=[N]
prev=1
for i in range(N):
    larger= larger +[N-i]*(L[i]-prev)
    prev=L[i]

total=0    
for i in range(N-2):
    low=L[:i+1]
    high=L[i+1:]
    for j in range(len(high)-1):
        diff = high[j+1]-high[0]
        if diff >= len(larger):
            count = 0
        else:
            count = max(larger[diff] - (N-i-1),0)
        total += count
        
print(total)

Submission status: Accepted

Solution code:
import bisect

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

res = (n * (n-1) * (n-2)) // 6
for i in range(n-2):
    a = l[i]
    for j in range(i+1, n-1):
        b = l[j]
        res -= n - bisect.bisect_left(l, a+b)

print(res)

Submission status: Accepted

Solution code:
def f_d():
    n, *l = map(int, open(0).read().split())

    l.sort()
    cnt = [n]*(l[-1]+l[-2]+1)
    for i in range(len(cnt)):
        o = 0
        for j in range(n):
            o = o+1 if i<l[j] else o
        cnt[i] = o

    o = 0
    for i in range(n):
        for j in range(i+1, n):
            ab1 = l[i]+l[j]
            ab2 = max(l[i], l[j]) - min(l[i], l[j])
            o += (cnt[ab2] - cnt[ab1-1])
            if ab2 < l[i] and l[i] < ab1:
                o -= 1
            if ab2 < l[j] and l[j] < ab1:
                o -= 1
    o = 0 if o<0 else o

    print(o//3)

if __name__ == "__main__":
    f_d()

Submission status: Accepted

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

import bisect

s = sorted(s)

res = 0
for i in range(n)[::-1]:
    for j in range(i)[::-1]:
        if s[j] <= s[i] / 2:
            break
        k = bisect.bisect_left(s, s[i]-s[j]+1)
        res += max(0, j-k)
print(res)

Submission status: Accepted

Solution code:
import sys
import bisect
readline = sys.stdin.readline
n = int(readline())
A = list(map(int,readline().split()))
memo1 = {}
memo2 = {}
A.sort()
memo1[A[0]+A[1]] =1
memo2[A[0]] =1
if A[1] in memo2:
    memo2[A[1]] +=1
else:
    memo2[A[1]] =1
ans = 0
for c in A[2:]:
    for l,amount in memo1.items():
        if c<l:
            ans +=amount
    for a,amount in memo2.items():
        ac = a+c
        if ac in memo1:
            memo1[ac] += memo2[a]
        else:
            memo1[ac] = memo2[a]
    if c in memo2:
        memo2[c] +=1
    else:
        memo2[c] =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):
        q = l[i]+l[j]
        p = bisect.bisect_left(l, q)
        ans += (p - j - 1)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
L = sorted([int(x) for x in input().split(' ')], reverse=True)

count = 0
while len(L) > 2:
    a = L.pop(0)
    ic = len(L) - 1
    for ib, b in enumerate(L):
        diff = a - b
        while L[ic] <= diff and ib < ic:
            ic -= 1
        count += ic - ib
        if ib >= ic:
            break

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(len(l)):
    for j in range(i + 1, len(l)):
        ans += max(bisect.bisect_left(l, l[i] + l[j])-j-1, 0)
print(ans)