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

Solution (Python):
from bisect import bisect_left,bisect_right
def main():
    n = int(input())
    d = [int(x) for x in input().split()]
    d = sorted(d)
    ans = 0
    for i in range(n):
        for j in range(i+1,n):
            flgi,flgj = 0,0
            a = d[i]+d[j]
            b = d[j]-d[i]

            left = bisect_left(d,a)
            right = bisect_right(d,b)
 
            if right<i+1<=left:
                flgi = 1
            if right<j+1<=left:
                flgj = 1
            ans += max((left-right)-(flgi+flgj),0)
    print(ans//3)
if __name__ == "__main__":
    main()

Solution (Python):
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)

from math import factorial
import heapq, bisect
import math
import itertools

import queue
from collections import deque



def main():
    num = int(input())
    data = list(map(int, input().split()))

    data.sort()
    dp = [0 for i in range(max(data) * 2 + 1)]

    count = Counter(data)

    for i in range(1, max(data) * 2 + 1):
        dp[i] = dp[i - 1] + count[i]

    count = sorted(count.items(), key=lambda x: x[0])
    ans = 0

    
    
    

    for i in range(len(count)):
        if count[i][1] >= 3:
            ans += (count[i][1] * (count[i][1] - 1) * (count[i][1] - 2)) // 6
        if count[i][1] >= 2:
            nokori = count[i][0] * 2 - 1
            ans += (count[i][1] * (count[i][1] - 1)) // 2 * (dp[nokori] - dp[count[i][0]])

        for j in range(i + 1, len(count)):
            if count[j][1] >= 2:
                ans += count[i][1] * (count[j][1] * (count[j][1] - 1)) // 2
            max_data = count[i][0] + count[j][0] - 1
            kari = count[i][1] * count[j][1] * (dp[max_data] - dp[count[j][0]])
            ans += kari

    print(ans)








if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
L = list(map(int,input().split()))
cnt = [0]*(3*10**3+1)
for i in range(N):
    cnt[L[i]] += 1
cum = [0]*(3*10**3+1)
for i in range(3*10**3):
    cum[i+1] = cum[i]+cnt[i+1]

ans = 0
for a in range(1,10**3+1):
    if cnt[a] == 0:
        continue
    for b in range(a+1,10**3+1):
        if cnt[b] == 0:
            continue
        ans  += (cum[a+b-1]-cum[b])*cnt[a]*cnt[b]

for a in range(10**3+1):
    if cnt[a] < 2:
        continue
    ans += ((cum[2*a-1]-cnt[a])*cnt[a]*(cnt[a]-1))//2

for a in range(10**3+1):
    if cnt[a] < 3:
        continue
    ans += (cnt[a]*(cnt[a]-1)*(cnt[a]-2))//6

print(ans)

Solution (Python):
from bisect import bisect_left

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

Solution (Python):
import sys
inf = float("inf")
from bisect import bisect_left,bisect_right

def get_array(): return list(map(int , sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()

n = int(input())
Arr = get_array()
Arr.sort()

ans = 0
for i in range(n):
    for j in range(i+1,n):
        new = Arr[i]+Arr[j]
        ans+=bisect_left(Arr[j+1:], new)
print(ans)

Solution (Python):
import collections
import heapq
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


N = int(input())
nums = list(map(int,input().split(" ")))
nums.sort()
ans = 0
di = collections.defaultdict(lambda :0)
for i in range(N):
    for j in range(i+1,N):
        key = nums[i] + nums[j]
        di[key] += 1
co = 0
for k,v in di.items():
    for temp in nums:
        if k <= temp:
            co += v

temp = combinations_count(N,3)
print(temp- co)

Solution (Python):
def main():
    n=int(input())
    d=list(map(int,input().split()))
    d.sort(reverse=True)
    
    
    
    ans=0
    for large in range(0,n-2):
        presmall=n-1
        for middle in range(large+1,n-1):
            if d[large]<d[middle]+d[presmall]:
                ans+=presmall-middle
                
            else:
                flag=False
                for i in range(presmall-1,middle,-1):
                    
                    if d[large]<d[middle]+d[i]:
                        presmall=i
                        flag=True
                        break
                if flag==False:
                    break
                else:
                    ans+=presmall-middle
                    
    print(ans)
main()

Solution (Python):
import bisect
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)

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

ans = 0
for i, a in enumerate(l):
    for j in range(i+1, n):
        b = l[j]
        lower = max(a-b, b-a)
        upper = a + b
        d = bisect.bisect_right(l, lower)
        u = bisect.bisect_left(l, upper)
        double = 0
        if d <= i < u:
            double += 1
        if d <= j < u:
            double += 1
        ans += max(0, u - d - double)

print(ans // 3)

Solution (Python):
N=int(input())
L=list(map(int,input().split()))
dic=[0]*1005
izyo=[0]*1005
for x in L:
	dic[x]+=1
ruike = 0
for x in range(1000,0,-1):
	ruike += dic[x]
	izyo[x] = ruike
ans=0
for a in range(1000,0,-1):
	
	
	ans+=dic[a]*(dic[a]-1)*(dic[a]-2)//6
	
	
	ans+=dic[a]*(dic[a]-1)//2*(izyo[1]-izyo[a])
	
	
	
	for b in range(a-1,a//2,-1):
		
		ans+=dic[a]*dic[b]*(dic[b]-1)//2
		
		
		ans+=dic[a]*dic[b]*(izyo[a-b+1]-izyo[b])
		
print(ans)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
a.sort()
ans = 0
for r in range(n-1,-1,-1):
  m = r
  for l in range(n):
    if l == m and m + 1 < r:
      m += 1
    else:
      while True:
        if a[l] + a[m-1] > a[r] and l < m-1:
          m -= 1
        else:
          break
    if l < m < r:
      ans += r - m
      
print(ans)

Solution (Python):
import sys

input = sys.stdin.readline

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

ans = 0
for f in range(N-2):
	fl = L[f]
	s = f+1
	t = f+2
	while s<=N-2:
		sl = L[s]
		
		if t<=N-1:
			while fl+sl>L[t]:
				t += 1
				if t==N: break
		ans += t-(s+1)
		
		s += 1

print(ans)

Solution (Python):


def input():
    import sys
    return sys.stdin.readline().rstrip()


def main():
    import math
    import collections
    import itertools
    import bisect

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

    ans = 0
    for l1 in range(n - 2):
        for l2 in range(l1 + 1, n - 1):
            check_l = ls[l1] + ls[l2]
            ans += max(bisect.bisect_left(ls, check_l) - (l2 + 1), 0)
            
            
    print(ans)


if __name__ == '__main__':
    main()

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

Solution (Python):
import bisect
import sys

input = sys.stdin.readline


def read_i():
    return list(map(int, input().split()))


n = int(input())
ls = sorted(read_i())
ls2 = ls[::-1]
res = 0
for i, x in enumerate(ls2):
    for j, y in enumerate(ls2[i + 1:], i + 1):
        if 2 * y < x:
            break
        res += n - j - 1 - bisect.bisect(ls[:-(j + 1)], x - y)
print(res)

Solution (Python):

from __future__ import division, print_function

import os
import sys
from bisect import bisect_right, bisect_left
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


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

    o = 0
    c = []

    for i in range(n):
        for j in range(i):
            a, b = l[i], l[j]

            s = bisect_right(l, a - b)
            e = bisect_left(l, a + b)

            o += max(0, e - max(s, i + 1))

    print(o)




BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")



if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
L = [int(l) for l in input().split()]

L.sort()

S = [0]*(L[-1]+L[-2]+2)

for i in range(N):
    if i < N-1:
        for j in range(L[i], L[i+1]):
            S[j] = i+1
    else:
        for j in range(L[-1], len(S)):
            S[j] = i+1
        
ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        m = abs(L[j]-L[i])
        M = L[j]+L[i]
        ans += S[M-1]-S[m]
        if m < L[i] < M:
            ans -= 1
        if m < L[j] < M:
            ans -= 1
            
print(ans//3)

Solution (Python):


import bisect

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

    n = 0
    for i, a in enumerate(L):
        for j, b in enumerate(L[i+1:]):
            n += max(0, bisect.bisect_left(L, a+b)-(j + i + 2))

    print(n)


if __name__ == '__main__':
    main()

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

Solution (Python):
N=int(input())
L=list(map(int,input().split()))
L.append(0)
L.append(10**9)
L.sort()



ans=0
import bisect

for a in range(1,N):
    for b in range(a+1,N+1):
        c=bisect.bisect_left(L,L[a]+L[b])
        if L[c]>=L[a]+L[b]:
            c-=1
        ans+=(c-b)
        
print(ans)

Solution (Python):


import bisect


def solve(N, L):
    L = sorted(L)
    llen = len(L)
    
    ans = 0
    for i in range(llen):
        for j in range(i+1, llen):
            k = bisect.bisect_left(L, L[i]+L[j], j+1)
            n = k - (j+1)
            
            ans += n
    return ans


if __name__ == '__main__':
    N = int(input())
    L = list(map(int, input().split()))

    ans = solve(N, L)

    print(ans)

Solution (Python):

import bisect


n = int(input())
l_list = input().split(" ")
l_int_list = []
for item in l_list:
    l_int_list.append(int(item))

l_int_list.sort()

count = 0


for i in range(len(l_int_list)):
    for j in range(i+1, len(l_int_list)):
        index = bisect.bisect_left(
            l_int_list, l_int_list[i]+l_int_list[j], j+1, len(l_int_list))
        count += index - j - 1

print(count)

Solution (Python):
import bisect as bis

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

res = 0
for i, a in enumerate(L):
    for k, b in enumerate(L[i + 1:]):
        j = k + i + 1

        left = b - a
        right = a + b

        index_l = bis.bisect_right(L, left, j)
        index_r = bis.bisect_left(L, right, j)
        if index_l == N - 1:
            break

        res += index_r - index_l - 1
print(res)