Problem: 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.

Submission attempts (in order):
from bisect import bisect_left

n = input()
ls = list(map(int, input().split())).sort
count = 0
for i in range(n - 2):
  for j in range(i + 1, n - 1):
    two_sides_sum = ls[i]+ ls[j]
    bi = bisect_left(ls, two_sides_sum)
    count += bi - j - 1
print(count)

import bisect
n = int(input())

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

count = 0

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

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

from bisect import bisect_left

n = int(input())
ls = list(map(int, input().split())).sort()
count = 0
for i in range(n - 2):
  for j in range(i + 1, n - 1):
    two_sides_sum = ls[i] + ls[j]
    bi = bisect_left(ls, two_sides_sum)
    count += bi-j-1
print(count)

from bisect import bisect_left

n = int(input())
ls = list(map(int, input().split())).sort()
count = 0
for i in range(n - 2):
  for j in range(i + 1, n - 1):
    two_sides_sum = ls[i] + ls[j]
    bi = bisect_left(ls, two_sides_sum)
    count += bi - j - 1
print(count)

import bisect

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

count = 0

for i in range(n - 2):
  a = ls[i]
  for j in range(i + 1, n - 1):
    b = ls[j]
    index = bisect.bisect_left(ls, a + b):
    count += index - j - 1
print(count)


from bisect import bisect_left

n = input()
ls = list(map(int, input().split()))
count = 0
for i in range(n - 2):
  for j in range(i + 1, n - 1):
    two_sides_sum = ls[i]+ ls[j]
    bi = bisect_left(ls, two_sides_sum)
    count += bi - j - 1
print(count)

from bisect import bisect_left

n = input()
ls = list(map(int, input().split()))
count = 0
for i in range(0, n - 2):
  for j in range(i + 1, n - 1):
    two_sides_sum = ls[i]+ ls[j]
    for k in range(j + 1, n):
      if two_sides_sum <= ls[k]:
        count += k - j - 1
        break
print(count)

from bisect import bisect_left

n = input()
ls = list(map(int, input().split()))
count = 0
for i in range(0, n - 2):
  for j in range(i + 1, n - 1):
    two_sides_sum = ls[i]+ ls[j]
    bi = bisect_left(ls, two_sides_sum)
    count += bi - j - 1
print(count)

n = input()
ls = list(map(int, input().split()))
count = 0
for i in range(0, n - 2):
  for j in range(i + 1, n - 1):
    two_sides_sum = i + j
    for k in range(j + 1, n):
      if two_sides_sum <= ls[k]:
        count += k - j - 1
        break
print(count)

from bisect import bisect_left

n = input()
ls = list(map(int, input().split())).sort()
count = 0
for i in range(n - 2):
  for j in range(i + 1, n - 1):
    two_sides_sum = ls[i]+ ls[j]
    bi = bisect_left(ls, two_sides_sum)
    count += bi - j - 1
print(count)

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

from bisect import bisect_left

n = int(input())
ls = list(map(int, input().split())).sort()
count = 0
for i in range(n - 2):
  for j in range(i + 1, n - 1):
    two_sides_sum = ls[i]+ ls[j]
    bi = bisect_left(ls, two_sides_sum)
    count += bi - j - 1
print(count)

import bisect
n = int(input())

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

count = 0

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

import bisect
n = int(input())

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

count = 0

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

# 2019-11-18 23:58:23(JST)
import sys
import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# import re
# import heapq
# import array
# from scipy.misc import comb # (default: exact=False)
# import numpy as np 


def main():
    n, *l = [int(x) for x in sys.stdin.read().split()]
    l.sort()

    c = collections.defaultdict(int)
    for i in range(n):
        c[l[i]] += 1
    
    # cumsum: count of {l[j]|l[j] <= l[i]}
    s = [0 for _ in range(l[-3] + l[-2] + 1)] 
    for i in range(l[-3] + l[-2]):
        s[i+1] = s[i] + c[i+1]

    count = 0
    # a <= b <= c
    for i in range(n-2):
        a = l[i]
        for j in range(i+1, n-1):
            b = l[j]
            
            count += s[a+b-1] - (j + 1) 

    print(count)




    

if __name__ == "__main__":
    main()


Verdicts: Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Accepted