Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque, defaultdict

S = input()

L = int(S)
S = S[::-1]
cnt = defaultdict(int)

tmp = 0
answer = 0
for i, s in enumerate(S):
    tmp += int(s) * 10 ** i
    if tmp % 2019 == 0:
        answer += cnt[0] + 1
    else:
        answer += cnt[tmp % 2019]
    cnt[tmp % 2019] += 1
    #print(tmp, answer)

print(answer)

Fixed submission:
from collections import deque, defaultdict

S = input()

L = int(S)
S = S[::-1]
cnt = defaultdict(int)

tmp = 0
answer = 0
for i, s in enumerate(S):
    tmp = (tmp + int(s) * pow(10, i, 2019)) % 2019
    #print(tmp)
    if tmp % 2019 == 0:
        answer += cnt[0] + 1
    else:
        answer += cnt[tmp % 2019]
    cnt[tmp % 2019] += 1
    #print(tmp, answer)

print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque, defaultdict

S = input()

L = int(S)
S = S[::-1]
cnt = defaultdict(int)

tmp = 0
answer = 0
for i, s in enumerate(S):
    tmp += int(s) * 10 ** i
    if tmp % 2019 == 0:
        answer += cnt[0] + 1
    else:
        answer += cnt[tmp % 2019]
    cnt[tmp % 2019] += 1
    #print(tmp, answer)

print(answer)

Fixed submission:
from collections import deque, defaultdict

S = input()

L = int(S)
S = S[::-1]
cnt = defaultdict(int)

tmp = 0
answer = 0
for i, s in enumerate(S):
    tmp = (tmp + int(s) * pow(10, i, 2019)) % 2019
    #print(tmp)
    if tmp % 2019 == 0:
        answer += cnt[0] + 1
    else:
        answer += cnt[tmp % 2019]
    cnt[tmp % 2019] += 1
    #print(tmp, answer)

print(answer)
Buggy python submission (verdict: Runtime Error):
root = [i for i in range(N + 1)]
size = [1] * (N + 1)
 
def find(x):
  y = root[x]
  if x == y:
    return x
  else:
    z = find(y)
    root[x] = z
    return z

def union(x, y):
  rx = find(x)
  ry = find(y)
  sx = size[rx]
  sy = size[ry]
  if rx == ry:
    return 0
  else:
    if sx >= sy:
      root[ry] = rx
      size[rx] = sx + sy
    else:
      root[rx] = ry
      size[ry] = sx + sy
    return sx * sy

Fixed submission:
N = int(input())

print(-(-N // 2))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = list(input())
Q = int(input())
query = [input().split() for _ in range(Q)]

bit = [[0 for _ in range(26)] for _ in range(N + 1)]

def bit_add(i, s, x):
    j = ord(s) - ord("a")
    while i <= N:
        bit[i][j] += x
        i += i & - i
        
def bit_sum(i):
    s = [0] * 26
    while i:
        for j in range(26):
            s[j] += bit[i][j]
        i -= i & -i
    return s
for i in range(1, N + 1):
    s = S[i - 1]
    bit_add(i, s, 1)

for x, y, z in query:
    if x == "1":
        y = int(y)
        bit_add(y, S[y - 1], -1)
        bit_add(y, z, 1)
        S[y - 1] = z
    if x == "2":
        answer = 0
        y, z = int(y) - 1, int(z)
        sum_y = bit_sum(y)
        sum_z = bit_sum(z)
        for i in range(26):
            if sum_z[i] - sum_y[i] > 0:
                answer += 1
        print(answer)


Fixed submission:
N = int(input())
S = list(input())
Q = int(input())
query = [input().split() for _ in range(Q)]

bit = [[0 for _ in range(26)] for _ in range(N + 1)]



def bit_add(i, s):
    ss = ord(s) - ord("a")
    while i <= N:
        bit[i][ss] += 1
        i += i & - i
def bit_add2(i, s):
    ss = ord(s) - ord("a")
    while i <= N:
        bit[i][ss] += -1
        i += i & - i
        
def bit_sum(i):
    s = [0] * 26
    while i:
        for j in range(26):
            s[j] += bit[i][j]
        i -= i & -i
    return s
for i in range(1, N + 1):
    s = S[i - 1]
    bit_add(i, s)



for x, y, z in query:
    if x == "1":
        y = int(y)
        bit_add2(y, S[y - 1])
        bit_add(y, z)
        S[y - 1] = z
    if x == "2":
        answer = 0
        y, z = int(y) - 1, int(z)
        yy = bit_sum(y)
        zz = bit_sum(z)
        #print(yy)
        #print(zz)
        for i in range(26):
            if zz[i] - yy[i] > 0:
                answer += 1
        print(answer)
    #print(S)
    #print(bit_sum(N))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.buffer.readline

K, Q = map(int, input().split())
D = list(map(int, input().split()))
NXM = [list(map(int, input().split())) for _ in range(Q)]

for N, X, M in NXM:
    E = [d % M for d in D]
    cnt, tmp = 0, 0
    for e in E:
        if e > 0:
            cnt += 1
            tmp += e
    cnt *= ((N - 1) // K)
    tmp *= ((N - 1) // K)
    for i in range((N - 1) % K):
        if E[i] > 0:
            cnt += 1
            tmp += E[i]
    tmp += X % M
    print(cnt - tmp // M)

Fixed submission:
import sys
input = sys.stdin.buffer.readline

K, Q = map(int, input().split())
D = list(map(int, input().split()))
NXM = [list(map(int, input().split())) for _ in range(Q)]

for N, X, M in NXM:
    E = [d % M for d in D]
    cnt0 = 0
    tmp0 = 0
    for e in E:
        if e > 0:
            cnt0 += 1
            tmp0 += e
    cnt = ((N - 1) // K) * cnt0
    tmp = ((N - 1) // K) * tmp0
    for i in range((N - 1) % K):
        if E[i] > 0:
            cnt += 1
        tmp += E[i]
    tmp += X % M
    print(cnt - tmp // M)
Buggy python submission (verdict: Runtime Error):
A = list(map(int, input().split()))
A = sorted(A)

if A[0] == A[1] and A[1] != A[2]:
    print("Yes")
elif A[0] != A[1] and A[1] == A[2]:
    print("Yes")
else
    print("No")


Fixed submission:
A = list(map(int, input().split()))
A = sorted(A)

if A[0] == A[1] and A[1] != A[2]:
    print("Yes")
elif A[0] != A[1] and A[1] == A[2]:
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.buffer.readline

H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
INF = 10 ** 15

dp = [INF] * (H + 1)
dp[0] = 0
for a, b in AB:
  for i in range(H):
    if dp[i] != INF:
      dp[min(i + a, H)] = min(dp[min(i + a, H)], dp[i] + b)

print(dp[-1])

Fixed submission:
import sys
input = sys.stdin.buffer.readline

H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

INF = 10 ** 15
dp = [INF] * (H + 1)
dp[0] = 0

answer = INF
for a, b in AB:
  for i in range(H + 1):
    if dp[i] != INF:
      if i + a < H:
        dp[i + a] = min(dp[i + a], dp[i] + b)
      else:
        answer = min(dp[i] + b, answer)
        
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.buffer.readline

H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

INF = 10 ** 15
dp = [INF] * H
dp[0] = 0
answer = INF
for a, b in AB:
  for i in range(H):
    if dp[i] != INF:
      if i + a < H:
        dp[i + a] = min(dp[i + a], dp[i] + b)
      else:
        answer = min(dp[i] + b, answer)

print(answer)

Fixed submission:
import sys
input = sys.stdin.buffer.readline

H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

INF = 10 ** 15
dp = [INF] * (H + 1)
dp[0] = 0

answer = INF
for a, b in AB:
  for i in range(H + 1):
    if dp[i] != INF:
      if i + a < H:
        dp[i + a] = min(dp[i + a], dp[i] + b)
      else:
        answer = min(dp[i] + b, answer)
        
print(answer)
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.buffer.readline

N, D, A = map(int, input().split())
XH = [list(map(int, input().split()))for _ in range(N)]

XH.sort()
print(XH)


for i in range(N):
    bit_add_sec(bit1, bit2, i, i, XH[i][1])


bit1 = [0] * (N + 1)
bit2 = [0] * (N + 1)

def bit_add(b, i, v):
    while i <= N:
        b[i] += v
        i += i & - i
        
def bit_sum(b, i):
    s = 0
    while i:
        s += b[i]
        i -= i & -i
    return s

def bit_add_sec(b1, b2, l, r, x):
    bit_add(b1, l, -x * (l - 1))
    bit_add(b2, l, x)
    bit_add(b1, r + 1, x * r)
    bit_add(b2, r + 1, -x)

def bit_sum_sec(b1, b2, l, r, x):
    res = 0
    res += bit_sum(b1, r) + bit_sum(b2, r) * r
    res -= bit_sum(b1, l - 1) + bit_sum(b2, l - 1) * (l - 1)
    return res


Fixed submission:
import sys
input = sys.stdin.buffer.readline

from bisect import bisect_right

N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]

XH.sort()
X = [x for x, h in XH]

check = [0] * (N + 1)


index = 0
pt = XH[index][0] + 2 * D
ht = (-(-XH[index][1] // A)) * A
minus = ht
answer = -(-XH[index][1] // A)
bi = bisect_right(X, pt)
check[bi] += ht

while 1:
  flag = 1
  for i in range(index, N):
    minus -= check[i]
    XH[i][1] -= minus
    check[i] = 0
    if XH[i][1] > 0:
      index = i
      flag = 0
      break
  if flag:
    break
  pt = XH[index][0] + 2 * D
  ht = (-(-XH[index][1] // A)) * A
  minus += ht
  answer += -(-XH[index][1] // A)
  bi = bisect_right(X, pt)
  check[bi] += ht
                 
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.buffer.readline

N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]

XH.sort()

index = 0
pt = XH[0][0] + 2 * D
ht = (-(-XH[0][1] // A)) * A
answer = -(-XH[0][1] // A)

while 1:
  for i in range(index, N):
    if XH[i][0] <= pt:
      XH[i][1] -= ht
    else:
      break
  flag = 1
  for i in range(index, N):
    if XH[i][1] > 0:
      pt = XH[i][0] + 2 * D
      ht = (-(-XH[i][1] // A)) * A
      answer += -(-XH[i][1] // A)
      index = i
      flag = 0
      break
  if flag == 1:
    break
                 
print(answer)

Fixed submission:
import sys
input = sys.stdin.buffer.readline

from bisect import bisect_right

N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]

XH.sort()
X = [x for x, h in XH]

check = [0] * (N + 1)


index = 0
pt = XH[index][0] + 2 * D
ht = (-(-XH[index][1] // A)) * A
minus = ht
answer = -(-XH[index][1] // A)
bi = bisect_right(X, pt)
check[bi] += ht

while 1:
  flag = 1
  for i in range(index, N):
    minus -= check[i]
    XH[i][1] -= minus
    check[i] = 0
    if XH[i][1] > 0:
      index = i
      flag = 0
      break
  if flag:
    break
  pt = XH[index][0] + 2 * D
  ht = (-(-XH[index][1] // A)) * A
  minus += ht
  answer += -(-XH[index][1] // A)
  bi = bisect_right(X, pt)
  check[bi] += ht
                 
print(answer)
Buggy python submission (verdict: Runtime Error):
import math

def get_circle_center_and_radius(x1, y1, x2, y2, x3, y3):
    """
    3点を通る円の中心と半径を取得
    """
    d = 2 * ((y1 - y3) * (x1 - x2) - (y1 - y2) * (x1 - x3))
    if d == 0:
      return (0, 0), 0
    x = ((y1 - y3) * (y1 ** 2 - y2 ** 2 + x1 ** 2 - x2 ** 2) - (y1 - y2) * (y1 ** 2 - y3 ** 2 + x1 ** 2 - x3 ** 2)) / d
    y = ((x1 - x3) * (x1 ** 2 - x2 ** 2 + y1 ** 2 - y2 ** 2) - (x1 - x2) * (x1 ** 2 - x3 ** 2 + y1 ** 2 - y3 ** 2)) / -d
    r = math.sqrt((x - x1) ** 2 + (y - y1) ** 2)
    return (x, y), r
  
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
answer = []
if N == 2:
  xy1, xy2 = XY
  x1, y1 = xy1
  x2, y2 = xy2
  answer.append(((x2 - x1)**2 + (y2 - y1)**2)**0.5 / 2)
else:
  for i in range(N):
    xi, yi = XY[i]
    for j in range(i + 1, N):
      xj, yj = XY[j]
      for k in range(j + 1, N):
        xk, yk = XY[k]
        xy0, r = get_circle_center_and_radius(xi, yi, xj, yj, xk, yk)
        x0, y0 = xy0
        
        if r:
          flag = 1
          for ii in range(N):
            xii, yii = XY[ii]
            if ((x0 - xii)**2 + (y0 - yii)**2)**0.5 > r:
              flag = 0
              break
          if flag:
            answer.append(r)
print(min(answer))  

Fixed submission:
import math

def get_circle_center_and_radius(x1, y1, x2, y2, x3, y3):
    """
    3点を通る円の中心と半径を取得
    """
    d = 2 * ((y1 - y3) * (x1 - x2) - (y1 - y2) * (x1 - x3))
    if d == 0:
      return (0, 0), 0
    x = ((y1 - y3) * (y1 ** 2 - y2 ** 2 + x1 ** 2 - x2 ** 2) - (y1 - y2) * (y1 ** 2 - y3 ** 2 + x1 ** 2 - x3 ** 2)) / d
    y = ((x1 - x3) * (x1 ** 2 - x2 ** 2 + y1 ** 2 - y2 ** 2) - (x1 - x2) * (x1 ** 2 - x3 ** 2 + y1 ** 2 - y3 ** 2)) / -d
    r = math.sqrt((x - x1) ** 2 + (y - y1) ** 2)
    return (x, y), r
  
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
answer = []
if N == 2:
  xy1, xy2 = XY
  x1, y1 = xy1
  x2, y2 = xy2
  answer.append(((x2 - x1)**2 + (y2 - y1)**2)**0.5 / 2)
else:
  for i in range(N):
    xi, yi = XY[i]
    for j in range(i + 1, N):
      xj, yj = XY[j]      
      r = ((xi - xj)**2 + (yi - yj)**2)**0.5/2
      x0, y0 = ((xi + xj) / 2, (yi + yj) / 2)
      flag = 1
      for ii in range(N):
        xii, yii = XY[ii]
        if ((x0 - xii)**2 + (y0 - yii)**2)**0.5 > r:
          flag = 0
          break
      if flag:
        answer.append(r)

  for i in range(N):
    xi, yi = XY[i]
    for j in range(i + 1, N):
      xj, yj = XY[j]
      for k in range(j + 1, N):
        xk, yk = XY[k]
        xy0, r = get_circle_center_and_radius(xi, yi, xj, yj, xk, yk)
        x0, y0 = xy0
        
        if r:
          flag = 1
          for ii in range(N):
            xii, yii = XY[ii]
            if ((x0 - xii)**2 + (y0 - yii)**2)**0.5 > r:
              flag = 0
              break
          if flag:
            answer.append(r)
print(min(answer))
Buggy python submission (verdict: Runtime Error):
N = int(input())
C = list(map(int, input().split()))
MOD = 10 ** 9 + 7

C.sort()
C = [0] + C

answer = 0
for i in range(1, N + 1):
  answer = (answer + C[i] * (pow(2, N - 1, MOD) + pow(2, N - 2, MOD) * (N - i))) % MOD
answer = (answer * pow(2, N, MOD)) % MOD

print(answer)

Fixed submission:
N = int(input())
C = list(map(int, input().split()))

MOD = 10 ** 9 + 7

C.sort()
C = C[::-1]

a0 = pow(2, N - 1, MOD)
d = pow(2, N - 2, MOD) if N - 2 >= 0 else 0
answer = 0
for i in range(N):
  answer = (answer + (a0 + d * i) * C[i]) % MOD
answer = (answer * pow(2, N, MOD)) % MOD
print(int(answer))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
C = list(map(int, input().split()))

MOD = 10 ** 9 + 7

C.sort()
C = C[::-1]

a0 = 2 ** (N - 1)
d = 2 ** (N - 2)
answer = 0
for i in range(N):
  answer = (answer + (a0 + d * i) * C[i]) % MOD
answer = (answer * pow(2, N, MOD)) % MOD
print(int(answer))

Fixed submission:
N = int(input())
C = list(map(int, input().split()))

MOD = 10 ** 9 + 7

C.sort()
C = C[::-1]

a0 = pow(2, N - 1, MOD)
d = pow(2, N - 2, MOD) if N - 2 >= 0 else 0
answer = 0
for i in range(N):
  answer = (answer + (a0 + d * i) * C[i]) % MOD
answer = (answer * pow(2, N, MOD)) % MOD
print(int(answer))
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
S=list(map(int,list(input())))

A=[0]*1000

for i in range(10):
  for ii in range(N):
    if i==S[ii]:
      for j in range(10):
        for jj in range(ii+1,N):
          if j==S[jj]:
            for k in range(10):
              for kk in range(jj+1,N):
                if k==S[kk]:
                  A[i*100+j*10+k]=1
                  break
print(sum(A))

Fixed submission:
N=int(input())
S=list(map(int,list(input())))
#print(S)

A=[[] for i in range(10)]

for i in range(N):
  A[S[i]].append(i)
#print(A)

cnt=0
for a in range(10):
  if len(A[a])==0:
    continue
  for c in range(10):
    if len(A[c])==0:
      continue
    cnt+=len(set(S[A[a][0]+1:A[c][-1]]))
print(cnt)
Buggy python submission (verdict: Runtime Error):
N, T = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

AB.sort()
dp = [0] * T
#print("AB:", AB)

answer = 0
for a, b in AB:
  for t in range(T-1, -1, -1):
    if dp[t]:
      if  a + t < T:
        dp[a + t] = max(dp[a + t], dp[t] + b)
        answer = max(answer, dp[a + t])
      else:
        answer = max(answer, dp[t] + b)
  if a < T:
    dp[a] = max(dp[a], b)
  answer = max(answer, b)
  #print("dp:", dp)
print(answer)      N, T = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

AB.sort()
dp = [0] * T
#print("AB:", AB)

answer = 0
for a, b in AB:
  for t in range(T-1, -1, -1):
    if dp[t]:
      if  a + t < T:
        dp[a + t] = max(dp[a + t], dp[t] + b)
        answer = max(answer, dp[a + t])
      else:
        answer = max(answer, dp[t] + b)
  if a < T:
    dp[a] = max(dp[a], b)
  answer = max(answer, b)
  #print("dp:", dp)
print(answer)      

Fixed submission:
N, T = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

AB.sort()
dp = [0] * T
#print("AB:", AB)

answer = 0
for a, b in AB:
  for t in range(T-1, -1, -1):
    if dp[t]:
      if  a + t < T:
        dp[a + t] = max(dp[a + t], dp[t] + b)
        answer = max(answer, dp[a + t])
      else:
        answer = max(answer, dp[t] + b)
  if a < T:
    dp[a] = max(dp[a], b)
  answer = max(answer, b)
  #print("dp:", dp)
print(answer)
Buggy python submission (verdict: Runtime Error):
import math
a,b,x=map(int,input().split())

if a*a*b%2==0:
  if a*a*b//2==x:
    print(0)
    exit()

if a*a*b/2>x:
    print(90-math.degrees(math.atan(2*x/(a*b*b))))
else:
  print(90-math.degrees(math.atan(a/(2*b-2*x/a/a))))

Fixed submission:
import math
a,b,x=map(int,input().split())
 
if a*b//2*a>=x:
  print(90-math.degrees(math.atan(2*x/(a*b*b))))
else:
  if a*b*b==x:
    print(0)
  else:
    print(90-math.degrees(math.atan(a/(2*b-2*x/a/a))))

Buggy python submission (verdict: Runtime Error):
import math
a,b,x=map(int,input().split())

if a*a*b/2>=x:
  if a*a*b/2==x:
    print(0)
  else:
    print(90-math.degrees(math.atan(2*x/(a*b*b))))
else:
  print(90-math.degrees(math.atan(a/(2*b-2*x/a/a))))

Fixed submission:
import math
a,b,x=map(int,input().split())
 
if a*b//2*a>=x:
  print(90-math.degrees(math.atan(2*x/(a*b*b))))
else:
  if a*b*b==x:
    print(0)
  else:
    print(90-math.degrees(math.atan(a/(2*b-2*x/a/a))))

Buggy python submission (verdict: Runtime Error):
import math
a,b,x=map(int,input().split())

if a*b//2*a>=x:
  print(90-math.degrees(math.atan(2*x/(a*b*b))))
else:
  print(90-math.degrees(math.atan(a/(2*b-2*x/a/a))))

Fixed submission:
import math
a,b,x=map(int,input().split())
 
if a*b//2*a>=x:
  print(90-math.degrees(math.atan(2*x/(a*b*b))))
else:
  if a*b*b==x:
    print(0)
  else:
    print(90-math.degrees(math.atan(a/(2*b-2*x/a/a))))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.buffer.readline

from heapq import heappush, heappop

N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))

A = sorted(A)
F = sorted(F)[::-1]

h = []
for i in range(N):
  a, f = A[i], F[i]
  heappush(h, (- a * f, a, f))
  
while K > 0:
  x, y, z = heappop(h)
  if x == 0:
    break
  else:
    heappush(h, (- (y - 1) * z, (y - 1), z))
    K -= 1
    
x, y, z = heappop(h)
print(-x)

Fixed submission:
import sys
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
readlines=sys.stdin.buffer.readlines

N,K=map(int,readline().split())
A=list(map(int,readline().split()))
F=list(map(int,readline().split()))
#print(N,K)
#print("A:",A)
#print(F)

A.sort()
F.sort(reverse=True)
#print("A:",A)
#print("F:",F)

left=-1
right=10**18
#right=10**3

while left+1<right:
  mid=(left+right)//2
  tmp=[0]*(N)
  for i in range(N):
    tmp[i]=max(A[i]-mid//F[i],0)
    
  if sum(tmp)<=K:
    right=mid
  else:
    left=mid
  #print("mid:",mid,",tmp:",tmp)
#print("left:",left,",mid:",mid,",right:",right)
print(right)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
L=list(map(int,input().split()))

L.sort(reverse=True)

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

Fixed submission:
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,-1,-1):
    if L[i]>=2*L[j]:
      break
    #print(L[i],L[j],bisect.bisect(L,L[i]-L[j]),j-bisect.bisect(L,L[i]-L[j]))
    ans+=j-bisect.bisect(L,L[i]-L[j])
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
L=list(map(int,input().split()))

L.sort(reverse=True)

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

Fixed submission:
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,-1,-1):
    if L[i]>=2*L[j]:
      break
    #print(L[i],L[j],bisect.bisect(L,L[i]-L[j]),j-bisect.bisect(L,L[i]-L[j]))
    ans+=j-bisect.bisect(L,L[i]-L[j])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int,input().split())
a=[]
c=[]
for i in range(M):
  aa,bb=map(int,input().split())
  a.append(aa)
  cc=["0"]*(N+1)
  d=list(map(int,input().split()))
  for dd in d:
    cc[dd]="1"
  c.append(int("".join(cc[1:]),2))
#print(a)
#print(c)

X=[10**10]*2**N
X[0]=0
for i in range(2**N):
  if X[i]<10**10:
    for j in range(M):
      if i|c[j]<2**N:
        X[i|c[j]]=min(X[i|c[j]],X[i]+a[j])
print(X[2**N-1] if X[2**N-1]!=10**10 else -1)

Fixed submission:
N,M=map(int,input().split())
a=[]
c=[]
for i in range(M):
  aa,bb=map(int,input().split())
  a.append(aa)
  cc=["0"]*(N+1)
  d=list(map(int,input().split()))
  for dd in d:
    cc[dd]="1"
  c.append(int("".join(cc[1:]),2))
#print(a)
#print(c)

X=[10**10]*2**N
X[0]=0
for i in range(2**N):
  if X[i]<10**10:
    for j in range(M):
      if i|c[j]<2**N:
        X[i|c[j]]=min(X[i|c[j]],X[i]+a[j])
print(X[2**N-1] if X[2**N-1]!=10**10 else -1)

Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int,input().split())
a=[]
c=[]
for i in range(M):
  aa,bb=map(int,input().split())
  a.append(aa)
  cc=["0"]*(N+1)
  d=list(map(int,input().split()))
  for dd in d:
    cc[dd]="1"
  c.append(int("".join(cc[1:]),2))
#print(a)
#print(c)

X=[10**10]*2**N
X[0]=0
for i in range(2**N):
  for j in range(M):
    if i|c[j]<2**N:
      X[i|c[j]]=min(X[i|c[j]],X[i]+a[j])
print(X[2**N-1] if X[2**N-1]!=10**10 else -1)

Fixed submission:
N,M=map(int,input().split())
a=[]
c=[]
for i in range(M):
  aa,bb=map(int,input().split())
  a.append(aa)
  cc=["0"]*(N+1)
  d=list(map(int,input().split()))
  for dd in d:
    cc[dd]="1"
  c.append(int("".join(cc[1:]),2))
#print(a)
#print(c)

X=[10**10]*2**N
X[0]=0
for i in range(2**N):
  if X[i]<10**10:
    for j in range(M):
      if i|c[j]<2**N:
        X[i|c[j]]=min(X[i|c[j]],X[i]+a[j])
print(X[2**N-1] if X[2**N-1]!=10**10 else -1)
Buggy python submission (verdict: Runtime Error):
H,W,A,B=map(int,input().split())
#print(H,W,A,B)

if H==1:
  print("1"*A+"0"*(W-A))
  exit()

if W==1:
  for i in range(H):
    if i<B:
      print("1")
    else:
      print("0")
  exit()
  
if A*H==B*W:
  X="1"*A+"0"*(W-A)
  for i in range(0,H*A,A):
    print(X[i%W:]+X[:i%W])
  exit()

print("No")

Fixed submission:
H,W,A,B=map(int,input().split())
#print(H,W,A,B)

h=[A*H+i*(W-2*A) for i in range(H)]
w=[B*W+i*(H-2*B) for i in range(W)]
#print(h)
#print(w)


for i,hh in enumerate(h):
  if hh in w:
    #print(i,w.index(hh))

    aa=[]
    for a in range(H-i):
      aa.append(W-A)
    for a in range(i):
      aa.append(A)
    #print("aa",aa)    

    bb=[]
    for b in range(W-w.index(hh)):
      bb.append(H-B)
    for b in range(w.index(hh)):
      bb.append(B)
    #print("bb",bb)    
    
    for a in range(H):
      pp=""
      for b in range(W):
        #print(a,b)
        if aa[a]>0 and bb[b]>0:
          pp+="1"
          aa[a]-=1
          bb[b]-=1
        else:
          pp+="0"
      print(pp)
    exit()

print("No")