Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A = sorted(A, reverse=True)[:K+1]
B = sorted(B, reverse=True)[:K+1]
C = sorted(C, reverse=True)[:K+1]

res = []

for i in A:
    for j in B:
        for k in C:
            res.append(i + j + k)

res = sorted(res, reverse=True)[:K+1]
for i in range(K):
    print(res[i])

Fixed submission:
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A = sorted(A, reverse=True)[:K+1]
B = sorted(B, reverse=True)[:K+1]
C = sorted(C, reverse=True)[:K+1]

res = []

for i in A:
    for j in B:
        res.append(i + j)
res2 = []
res = sorted(res, reverse=True)[:K+1]

for i in C:
    for re in res:
        res2.append(i + re)
        
res2 = sorted(res2, reverse=True)[:K+1]
          

for i in range(K):
    print(res2[i])
Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split())
S = input()
lr = [list(map(int, input().split())) for _ in range(Q)]

box = []
for i in range(N):
    box.append(S[:i+1].count("AC"))

for i, j in lr:
    print(box[j-1] - box[i-1])

Fixed submission:
N, Q = map(int, input().split())
S = input()
l, r = [], []
t = [0] * (N+1)
for i in range(N):
    t[i + 1] = t[i] +(1 if S[i:i+2] == 'AC' else 0)
for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])

Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split())
S = input()
l, r = [], []
for i in range(Q):
    temp, temp2 = map(int, input().split())
    l.append(temp)
    r.append(temp2)

counter = 0
for i in range(len(l)):
    for j in range(l[i]-1, r[i]-1):
        temp3 = S[j:j+2]
        if j == len(S):
            continue
        elif j == r[i]:
            continue
        elif temp3 == "AC":
            counter += 1
    print(counter)
    counter = 0


Fixed submission:
N, Q = map(int, input().split())
S = input()
l, r = [], []
t = [0] * (N+1)
for i in range(N):
    t[i + 1] = t[i] +(1 if S[i:i+2] == 'AC' else 0)
for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
AB = []
for i in range(N):
    AB.append(list(map(int, input().split())))
    
AB.sort(key=lambda x:x[0])

kane = 0
hon = 0
for i in range(N):
    if hon + AB[i][1] < M:
        hon += AB[i][1]
        kane += AB[i][0] * AB[i][1]
        continue
    elif hon + AB[i][1] == M:
        hon += AB[i][1]
        kane += AB[i][0] * AB[i][1]
        print(kane)
        break
    else:
        for j in range(AB[i][1]):
            hon += 1
            kane += AB[i][0]
            if hon == M:
                print(kane)
                break

Fixed submission:
N, M = map(int, input().split())
AB = []
for i in range(N):
    AB.append(list(map(int, input().split())))
    
AB.sort(key=lambda x:x[0])

kane = 0
hon = 0
for i in range(N):
    if hon + AB[i][1] < M:
        hon += AB[i][1]
        kane += AB[i][0] * AB[i][1]
        continue
    elif hon + AB[i][1] == M:
        hon += AB[i][1]
        kane += AB[i][0] * AB[i][1]
        print(kane)
        break
    else:
        kane += (M - hon) * AB[i][0]
        print(kane)
        break

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
AB = []
for i in range(N):
    AB.append(list(map(int, input().split())))
    
AB.sort(key=lambda x:x[0])

kane = 0
hon = 0
for i in range(N):
    for j in range(AB[i][1]):
        hon += 1
        kane += AB[i][0]
        if hon == M:
            print(kane)
            break

Fixed submission:
N, M = map(int, input().split())
AB = []
for i in range(N):
    AB.append(list(map(int, input().split())))
    
AB.sort(key=lambda x:x[0])

kane = 0
hon = 0
for i in range(N):
    if hon + AB[i][1] < M:
        hon += AB[i][1]
        kane += AB[i][0] * AB[i][1]
        continue
    elif hon + AB[i][1] == M:
        hon += AB[i][1]
        kane += AB[i][0] * AB[i][1]
        print(kane)
        break
    else:
        kane += (M - hon) * AB[i][0]
        print(kane)
        break
Buggy python submission (verdict: Time Limit Exceeded):
S = str(input())
Smae = S
while True:
    S = S.replace('01', '')
    S = S.replace('10', '')
    if '01' not in S and '10' not in S:
        break
print(len(Smae) - len(S))

Fixed submission:
S = str(input())

C0, C1 = 0, 0
for i in S:
    if i == "0":
        C0 += 1
    else:
        C1 += 1
mini = min(C0, C1)
print(2 * mini)
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))

As = sorted(A)
As = [a%As[0] if a%As[0] != 0 else As[0] for a in As]
As = sorted(As)

def judge(tmp_one, tmp_two):
    flg = 1
    
    while flg:
        if tmp_two % tmp_one == 0:
            tmp_two = tmp_one
        else:
            tmp_two = tmp_two % tmp_one
            
        if tmp_one % tmp_two == 0:
            tmp_one = twp_two
        else:
            tmp_one = tmp_one % tmp_two
        if tmp_one == tmp_two:
            flg = 0
            
        return tmp_one
tmp_one = As[0]
for i in range(1, N):
    if i == N  - 1:
        tmp_two = As[i]
    elif As[i] != As[0]:
        tmp_two = As[i]
        break
        
ans = judge(tmp_one, tmp_two)
print(ans)

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

As = sorted(A)
As = [a%As[0] if a%As[0] != 0 else As[0] for a in As]
As = sorted(As)

def judge(tmp_one, tmp_two):
    flg = 1

    while flg:
        if tmp_two%tmp_one == 0:
            tmp_two = tmp_one
        else:
            tmp_two = tmp_two%tmp_one

        if tmp_one%tmp_two == 0:
            tmp_one = tmp_two
        else:
            tmp_one = tmp_one%tmp_two
        if tmp_one == tmp_two:
            flg = 0

    return tmp_one

tmp_one = As[0]
for i in range(1, N):
    if i == N - 1:
        tmp_two = As[i]
    elif As[i] != As[0]:
        tmp_two = As[i]
        break

ans = judge(tmp_one, tmp_two)
print(ans)

Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

print(gcd(*A))

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

As = sorted(A)
As = [a%As[0] if a%As[0] != 0 else As[0] for a in As]
As = sorted(As)

def judge(tmp_one, tmp_two):
    flg = 1

    while flg:
        if tmp_two%tmp_one == 0:
            tmp_two = tmp_one
        else:
            tmp_two = tmp_two%tmp_one

        if tmp_one%tmp_two == 0:
            tmp_one = tmp_two
        else:
            tmp_one = tmp_one%tmp_two
        if tmp_one == tmp_two:
            flg = 0

    return tmp_one

tmp_one = As[0]
for i in range(1, N):
    if i == N - 1:
        tmp_two = As[i]
    elif As[i] != As[0]:
        tmp_two = As[i]
        break

ans = judge(tmp_one, tmp_two)
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
dpa = [0] * N
dpb = dpa.copy()
dpc = dpa.copy()

a, b, c = map(int, input().split())
dpa[0] = a
dpb[0] = b
dpc[0] = c
for i in range(1, N):
    a, b, c = map(int, input().split())
    dpa[i] = max(dpb[i-1] + a, dpc[i-1] + a)
    dpb[i] = max(dpa[i-1] + b, dpc[i-1] + b)
    dpc[i] = max(dpa[i-1] + c, dpb[i-1] + c)

print(max(dpa[N-1], dpb[N-1], dpc[N-1]))

Fixed submission:
# Educational DP Contest C-Vacation

def solve():
    n = int(input())
    dpa = [0] * n
    dpb = [0] * n
    dpc = [0] * n
    
    a, b, c = list(map(int, input().split()))
    dpa[0] = a
    dpb[0] = b
    dpc[0] = c
    for i in range(1, n):
        a, b, c = list(map(int, input().split()))
        dpa[i] = max(dpb[i-1] + a, dpc[i-1] + a)
        dpb[i] = max(dpa[i-1] + b, dpc[i-1] + b)
        dpc[i] = max(dpb[i-1] + c, dpa[i-1] + c)
    return(max(dpa[-1], dpb[-1], dpc[-1]))

if __name__ == "__main__":
    print(solve())
Buggy python submission (verdict: Runtime Error):
 N, W = map(int, input().split())
 wv = [list(map(int, input().split())) for _ in range(N)]

 dp = []
 for _ in range(N+1):
     dp.append([0] * (W+1))

for i in range(N):
    for j in range(W+1):
        if j >= wv[i][0]:
            dp[i+1][j] = max(dp[i][j], dp[i][j - wv[i][0]] + wv[i][1])
        else:
            dp[i+1][j] = dp[i][j]
print(dp[N][W])

Fixed submission:
# Educational DP Contest D-knapsack

def knapsack(N, W, wv):
    # initialize
    dp = [list(0 for _ in range(W+1)) for j in range(N+1)]
    
    # DP
    for i in range(N):
        for j in range(W+1):
            if j >= wv[i][0]:
                dp[i+1][j] = max(dp[i][j], dp[i][j - wv[i][0]] + wv[i][1])
            else:
                dp[i+1][j] = dp[i][j]
    return dp[N][W]

if __name__ == "__main__":
    N, W = map(int, input().split())
    wv = []
    for _ in range(N):
        wv.append(list(map(int, input().split())))
    print(knapsack(N, W, wv))
Buggy python submission (verdict: Runtime Error):
# Longest path
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(int, input().split())
    graph[x-1].append(y-1)
dp = [-1 for _ in range(N)]

def rec(c):
    if dp[c] != -1:
        return dp[c]
    res = 0
    for i in graph[c]:
        res = max(res, rec(i) + 1)
    dp[c] = res
    return res

for i in range(N):
    rec(i)
print(max(dp))

Fixed submission:
import sys
sys.setrecursionlimit(10000)
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(int, input().split())
    graph[x-1].append(y-1) # 有向グラフ

# メモ化再帰
dp = [-1 for _ in range(100100)]
def rec(v):
    if dp[v] != -1:
        return dp[v]
    res = 0
    for i in graph[v]:
        res = max(res, rec(i) + 1)
    dp[v] = res
    return res

res = 0
for v in range(N):
    res = max(res, rec(v))
print(res)

Buggy python submission (verdict: Runtime Error):
sys.setrecursionlimit(10000)
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(int, input().split())
    graph[x-1].append(y-1) # 有向グラフ

# メモ化再帰
dp = [-1 for _ in range(100100)]
def rec(v):
    if dp[v] != -1:
        return dp[v]
    res = 0
    for i in graph[v]:
        res = max(res, rec(i) + 1)
    dp[v] = res
    return res

res = 0
for v in range(N):
    res = max(res, rec(v))
print(res)

Fixed submission:
import sys
sys.setrecursionlimit(10000)
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(int, input().split())
    graph[x-1].append(y-1) # 有向グラフ

# メモ化再帰
dp = [-1 for _ in range(100100)]
def rec(v):
    if dp[v] != -1:
        return dp[v]
    res = 0
    for i in graph[v]:
        res = max(res, rec(i) + 1)
    dp[v] = res
    return res

res = 0
for v in range(N):
    res = max(res, rec(v))
print(res)

Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(int, input().split())
    graph[x-1].append(y-1) # 有向グラフ

# メモ化再帰
dp = [0 for _ in range(100100)]
def rec(v):
    if dp[v] != -1:
        return dp[v]
    res = 0
    for i in graph[v]:
        res = max(res, rec(i) + 1)
    dp[v] = res
    return res

for i in range(N):
    dp[i] = -1
res = 0
for v in range(N):
    res = max(res, rec(v))
print(res)

Fixed submission:
import sys
sys.setrecursionlimit(10000)
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(int, input().split())
    graph[x-1].append(y-1) # 有向グラフ

# メモ化再帰
dp = [-1 for _ in range(100100)]
def rec(v):
    if dp[v] != -1:
        return dp[v]
    res = 0
    for i in graph[v]:
        res = max(res, rec(i) + 1)
    dp[v] = res
    return res

res = 0
for v in range(N):
    res = max(res, rec(v))
print(res)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
a = list(map(int, input().split()))
suma = [0, a[0]]
for i in range(1, N):
    suma.append(suma[-1] + a[i])
inf = float("inf")
dp = [[-1 for i in range(N+1)] for j in range(N+1)]
# dp[i][j]は区間[i, j)での最小のコスト

# メモ化再帰
def rec(l, r):
    if r - l == 0:
        dp[l][r] = 0
        return 0
    elif r - l == 1:
        dp[l][r] = a[l]
        return a[l]

    # r - l >= 2である
    # iを媒介にdpを貪欲に探索する。
    res = inf
    for pos in range(l+1, r):
        tmp = 0
        if pos - l > 1:
            tmp += rec(l, pos) + suma[pos] - suma[l]
        else:
            tmp += rec(l, pos)
        if r - pos > 1:
            tmp += rec(pos, r) + suma[r] - suma[pos]
        else:
            tmp += rec(pos, r)
        res = min(res, tmp)
    dp[l][r] = res
    return res

print(rec(0, N))

Fixed submission:
import sys
sys.setrecursionlimit(10000)
N = int(input())
a = list(map(int, input().split()))
suma = [0, a[0]]
for i in range(1, N):
    suma.append(suma[-1] + a[i])
inf = float("inf")
dp = [[-1 for i in range(N+1)] for j in range(N+1)]
# dp[i][j]は区間[i, j)での最小のコスト

# メモ化再帰
def rec(l, r):
    if r - l == 0:
        dp[l][r] = 0
        return 0
    elif r - l == 1:
        dp[l][r] = a[l]
        return a[l]

    if dp[l][r] != -1:
        return dp[l][r]

    # r - l >= 2である
    # iを媒介にdpを貪欲に探索する。
    res = inf
    for pos in range(l+1, r):
        tmp = 0
        if pos - l > 1:
            tmp += rec(l, pos) + suma[pos] - suma[l]
        else:
            tmp += rec(l, pos)
        if r - pos > 1:
            tmp += rec(pos, r) + suma[r] - suma[pos]
        else:
            tmp += rec(pos, r)
        res = min(res, tmp)
    dp[l][r] = res
    return res

print(rec(0, N))
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
PY = []
for i in range(M):
    PY.append(list(map(int, input().split())))
    
def kansu(a, ans):
    if a in ans:
        temp = int(a[6:])
        temp += 1
        temp = str(temp).zfill(6)
        b = a[:6] + temp
        response = kansu(b, ans)
    else:
        response = a
    return response
    
    
sort_PY = sorted(PY, key=lambda x: x[1])
ans = [""] * M
for i, j in enumerate(sort_PY):
    
    for k, l in enumerate(PY):
        if sort_PY[i][1] == PY[k][1]:
            index = k
        
    a = str(sort_PY[i][0]).zfill(6) + str(1).zfill(6)
    response = kansu(a, ans)
    ans[index] = response
for i in ans:
    print(i)

Fixed submission:
N, M = map(int, input().split())
PY = []
for i in range(M):
    PY.append(list(map(int, input().split())) + [i])
    
PY.sort(key = lambda x:x[1])
PY.sort(key = lambda x:x[0])
    
bef = 0
state = 0
retstr = ''
triple = []
for i in PY:
    if (i[0] != bef):
        bef = i[0]
        state = 1
        triple.append([i[0], i[1], i[2], str(i[0]).rjust(6, '0') + str(state).rjust(6, '0')])
    else:
        state += 1
        triple.append([i[0], i[1], i[2], str(i[0]).rjust(6, '0') + str(state).rjust(6, '0')])
triple.sort(key = lambda x:x[2])
for i in triple:
    print(i[3])
Buggy python submission (verdict: Time Limit Exceeded):
import math


def lcm(x, y):
    return (x * y) // math.gcd(x, y)


N, M = map(int, input().split())
S = input()
T = input()
L = lcm(N, M)
box = ["" for _ in range(L)]
for i in range(N):
    box[i * (L // N)] = S[i]
for j in range(M):
    temp = j * (L // M)
    if box[temp] == "":
        box[temp] = T[j]
    elif box[temp] == T[j]:
        continue
    else:
        print(-1)
        break
else:
    print(L)

Fixed submission:
import math


def lcm(x, y):
    return (x * y) // math.gcd(x, y)


N, M = map(int, input().split())
S = input()
T = input()
L = lcm(N, M)
G = math.gcd(N, M)
for i in range(G):
    if S[N//G * i] != T[M//G * i]:
        print(-1)
        break
else:
    print(L)
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict

S = input()
T = input()
L=len(S)
dds = defaultdict(int)
ddt = defaultdict(int)
for i in range(L):
  s = S[i]
  t = T[i]
  if dds[s] == 0:
    dds[s] = t
  else:
    if dds[s] != t:
      print("No")
      sys.exit()
      
  if ddt[t] == 0:
    ddt[t] = s
  else:
    if ddt[t] != s:
      print("No")
      sys.exit()
      
print("Yes")

Fixed submission:
#ABC110 C String Transformation

S = input()
T = input()

StoT = {}
TtoS = {}

for s, t in zip(S, T):
    if s in StoT.keys():
        if StoT[s] != t:
            print('No')
            exit()
    elif t in TtoS.keys():
        if TtoS[t] != s:
            print('No')
            exit()
    else:
        StoT[s] = t
        TtoS[t] = s
        
print('Yes')

Buggy python submission (verdict: Time Limit Exceeded):
S = str(input())
T = str(input())

s_box = []
t_box = []

for i in range(len(S)):
    if i >= len(S):
        break
    s_box.append(S.count(S[i]))
    t_box.append(T.count(T[i]))
    if s_box[i] == t_box[i]:
        S.replace(S[i], "")
        T.replace(T[i], "")
        continue
    else:
        print('No')
        exit()
print('Yes')

Fixed submission:
#ABC110 C String Transformation

S = input()
T = input()

StoT = {}
TtoS = {}

for s, t in zip(S, T):
    if s in StoT.keys():
        if StoT[s] != t:
            print('No')
            exit()
    elif t in TtoS.keys():
        if TtoS[t] != s:
            print('No')
            exit()
    else:
        StoT[s] = t
        TtoS[t] = s
        
print('Yes')

Buggy python submission (verdict: Time Limit Exceeded):
S = str(input())
T = str(input())

s_box = []
t_box = []

for i in range(len(S)):
    s_box.append(S.count(S[i]))
    t_box.append(T.count(T[i]))
    if s_box[i] == t_box[i]:
        continue
    else:
        print('No')
        exit()
print('Yes')

Fixed submission:
#ABC110 C String Transformation

S = input()
T = input()

StoT = {}
TtoS = {}

for s, t in zip(S, T):
    if s in StoT.keys():
        if StoT[s] != t:
            print('No')
            exit()
    elif t in TtoS.keys():
        if TtoS[t] != s:
            print('No')
            exit()
    else:
        StoT[s] = t
        TtoS[t] = s
        
print('Yes')
Buggy python submission (verdict: Time Limit Exceeded):
# ABC102 C-Linear Approximation

import numpy as np

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

As = [0]*N
for i, j in enumerate(A):
    As[i] = j - (i+1)

As = np.array(As)
temp = np.median(As)
# temp = sum(As) // len(As)
ans1, ans2, ans3 = 0, 0, 0
for i in As:
    ans1 += abs(i - temp)
    ans2 += abs(i - (temp+1))
    ans3 += abs(i - (temp-1))
    
print(int(min(ans1, ans2, ans3)))

Fixed submission:
# ABC102 C-Linear Approximation

N = int(input())
A = list(int(s) for s in input().split())
ami = [A[i] - i - 1 for i in range(N)]
ami.sort()
b = ami[N // 2]
print(sum(abs(v - b) for v in ami))
Buggy python submission (verdict: Time Limit Exceeded):
A, B, C, K = map(int, input().split())

if A == B == C:
    print(0)
    exit()

for i in range(K):
    nA = B + C
    nB = A + C
    nC = A + B
    A, B, C = nA, nB, nC
    if abs(A - B) >= int(1e18):
        print("Unfair")
        break
else:
    print(A - B)

Fixed submission:
A, B, C, K = map(int, input().split())

if K % 2 == 0:
    if abs(A - B) >= int(1e18):
        print("Unfair")
    else:
        print(A - B)
else:
    if abs(A - B) >= int(1e18):
        print("Unfair")
    else:
        print(B - A)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
X = list(map(int, input().split()))
Xc = X.copy()
Xc.sort()

for i in range(N):
    ind = Xc.index(X[i])
    if ind < (N // 2):
        print(Xc[N // 2])
    else:
        print(Xc[N // 2 - 1])

Fixed submission:
N = int(input())
X = list(map(int, input().split()))
Xc = X.copy()
Xc.sort()

Xcmed = Xc[N//2]

for i in range(N):
    if X[i] < Xcmed:
        print(Xc[N // 2])
    else:
        print(Xc[N // 2 - 1])

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

for i in range(N):
    Xc = X.copy()
    del Xc[i]
    Xc.sort()
    print(Xc[(N-1)//2])


Fixed submission:
N = int(input())
X = list(map(int, input().split()))
Xc = X.copy()
Xc.sort()

Xcmed = Xc[N//2]

for i in range(N):
    if X[i] < Xcmed:
        print(Xc[N // 2])
    else:
        print(Xc[N // 2 - 1])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
a = list(map(int, input().split()))
seta = set(a)

ans = 0
for e in seta:
    ce = a.count(e)
    if e < ce:
        ans += ce - e
    elif e > ce:
        ans += ce

print(ans)

Fixed submission:
from collections import Counter


N = int(input())
a = list(map(int, input().split()))
S = Counter(a)

ans = 0

for a, b in list(S.items()):
    if a < b:
        ans += b - a
    elif a > b:
        ans += b

print(ans)

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

el = []
for e in seta:
    el.append([e, a.count(e)])

ans = 0
for n, c in el:
    if c > n:
        ans += c - n
    elif c < n:
        ans += c

print(ans)

Fixed submission:
from collections import Counter


N = int(input())
a = list(map(int, input().split()))
S = Counter(a)

ans = 0

for a, b in list(S.items()):
    if a < b:
        ans += b - a
    elif a > b:
        ans += b

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
B.sort()
B = [0] + B
C.sort()
C = [0] + C
# A > B > Cなる組み合わせの数を求める
ans = 0

for a in A:
    left, right = 0, N
    if a >= B[N]:
        continue
    while abs(left - right) > 1:
        mid = (left + right) // 2
        if B[mid] > a:
            right = mid
        else:
            left = mid
    nB = B[right:]
    for nb in nB:
        left2, right2 = 0, N
        if nb >= C[N]:
            continue
        while abs(left2 - right2) > 1:
            mid2 = (left2 + right2) // 2
            if C[mid2] > nb:
                right2 = mid2
            else:
                left2 = mid2
        ans += N - right2 + 1
print(ans)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
C.sort()
ans = 0

for b in B:
    if b <= A[0] or b >= C[N-1]:
        continue
    # Aに対して
    l, r = -1, N
    while abs(l - r) > 1:
        mid = (l + r) // 2
        if A[mid] < b:
            l = mid
        else:
            r = mid
    # Bに対して
    l2, r2 = -1, N
    while abs(l2 - r2) > 1:
        mid = (l2 + r2) // 2
        if C[mid] > b:
            r2 = mid
        else:
            l2 = mid
    ans += (l+1) * (N - r2)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
D = list(map(int, input().split()))
M = int(input())
T = list(map(int, input().split()))

for t in T:
    if not D:
        break
    if t in D:
        D.remove(t)
    else:
        print("NO")
        break
else:
    print("YES")

Fixed submission:
from collections import defaultdict

N = int(input())
D = list(map(int, input().split()))
M = int(input())
T = list(map(int, input().split()))
Ddic = defaultdict(int)
Tdic = defaultdict(int)

for d in D:
    Ddic[d] += 1
for t in T:
    Tdic[t] += 1
for n, v in Tdic.items():
    Ddic[n] -= v
dv = Ddic.values()
if all(i >= 0 for i in dv):
    print("YES")
else:
    print("NO")
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
A = sorted(A, reverse=True)

n4 = []
n2 = set()
for a in A:
    if A.count(a) >= 4:
        if len(n4) >= 1:
            break
        n4.append(a)
    elif A.count(a) >= 2:
        if len(n2) >= 2:
            break
        n2.add(a)
n2 = list(n2)

ans = 0
if len(n2) >= 2:
    ans = n2[0] * n2[1]
for i in n4:
    for j in n2:
        ans = max(ans, i*j)
if len(n4) >= 1:
    ans = max(ans, n4[0] ** 2)

print(ans)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
A = sorted(A, reverse=True)
kouho = set()

for i in range(N):
    if i == 0:
        continue
    elif A[i-1] == A[i]:
        kouho.add(A[i])
        if A.count(A[i]) >= 4 or len(kouho) >= 2:
            break
else:
    ans = 0

kouho = list(kouho)

if len(kouho) >= 2:
    ans = kouho[0] * kouho[1]
elif len(kouho) == 1:
    ans = kouho[0] ** 2

print(ans)