Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
from bisect import bisect_left

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

num1 = bisect_left(xs, 0)
num2 = N - num1

d1s = [0] + [-x for x in xs[:num1]][::-1]
d2s = [0] + xs[num1:]

ans = float('inf')
for i in range(max(0, K - num2), num1 + 1):
    d1, d2 = d1s[i], d2s[K - i]
    ans = min(ans, d1 + d2 + min(d1, d2))

print(ans)


Fixed submission:
from bisect import bisect_left

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

num1 = bisect_left(xs, 0)
num2 = N - num1

d1s = [0] + [-x for x in xs[:num1]][::-1]
d2s = [0] + xs[num1:]

ans = float('inf')
for i in range(max(0, K - num2), min(num1, K) + 1):
    d1, d2 = d1s[i], d2s[K - i]
    ans = min(ans, d1 + d2 + min(d1, d2))

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    N = int(input())
    As = list(map(int, input().split()))

    pow2 = 2**N

    anss = []
    ans = 0
    setMax2s = [set([0])]
    for S in range(1, pow2):
        setMax2 = set([S])
        for i in range(N):
            if (S>>i)&1:
                S0 = S^(1<<i)
                setMax2 |= setMax2s[S0]
        Bs = sorted(setMax2, key=lambda x: As[x], reverse=True)
        i, j = Bs[:2]
        ans2 = As[i]+As[j]
        if ans2 > ans:
            ans = ans2
        anss.append(ans)
        setMax2 = set([i, j])
        setMax2s.append(setMax2)

    print('\n'.join(map(str, anss)))


solve()


Fixed submission:
def solve():
    N = int(input())
    As = list(map(int, input().split())) + [0]

    pow2 = 2**N

    anss = []
    ans = 0
    max2s = [[0, -1]]
    for S in range(1, pow2):
        m1, m2 = S, -1
        for i in range(N):
            if (S>>i)&1:
                S0 = S^(1<<i)
                i1, i2 = max2s[S0]
                if m1 == i1:
                    m2 = m2 if As[m2] >= As[i2] else i2
                elif As[m1] >= As[i1]:
                    m2 = m2 if As[m2] >= As[i1] else i1
                else:
                    m2 = m1 if As[m1] >= As[i2] else i2
                    m1 = i1
        ans2 = As[m1]+As[m2]
        if ans2 > ans:
            ans = ans2
        anss.append(ans)
        max2s.append([m1, m2])

    print('\n'.join(map(str, anss)))


solve()

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

    pow2 = 2**N

    anss = []
    ans = 0
    setMax2s = [set([0])]
    for S in range(1, pow2):
        setMax2 = set([S])
        for i in range(N):
            if (S>>i)&1:
                S0 = S^(1<<i)
                setMax2 |= setMax2s[S0]
        Bs = sorted(setMax2, key=lambda x: As[x], reverse=True)
        i, j = Bs[:2]
        ans2 = As[i]+As[j]
        if ans2 > ans:
            ans = ans2
        anss.append(ans)
        setMax2 = set([i, j])
        setMax2s.append(setMax2)

    print('\n'.join(map(str, anss)))


solve()


Fixed submission:
def solve():
    N = int(input())
    As = list(map(int, input().split())) + [0]

    pow2 = 2**N

    anss = []
    ans = 0
    max2s = [[0, -1]]
    for S in range(1, pow2):
        m1, m2 = S, -1
        for i in range(N):
            if (S>>i)&1:
                S0 = S^(1<<i)
                i1, i2 = max2s[S0]
                if m1 == i1:
                    m2 = m2 if As[m2] >= As[i2] else i2
                elif As[m1] >= As[i1]:
                    m2 = m2 if As[m2] >= As[i1] else i1
                else:
                    m2 = m1 if As[m1] >= As[i2] else i2
                    m1 = i1
        ans2 = As[m1]+As[m2]
        if ans2 > ans:
            ans = ans2
        anss.append(ans)
        max2s.append([m1, m2])

    print('\n'.join(map(str, anss)))


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

Mat = [[0] * (N - 1) + [N] for d in range(20)]
prev = [-1] * 20

for i, A in enumerate(As):
    binA = format(A, 'b').zfill(20)
    for d in range(20):
        if binA[d] == '1':
            if prev[d] != -1:
                Mat[d][prev[d]] = i
            prev[d] = i

for d in range(20):
    for i in reversed(range(N - 1)):
        if Mat[d][i] == 0:
            Mat[d][i] = Mat[d][i + 1]

minM = list(map(min, *Mat))

print(sum(minM) - N * (N - 1) // 2)


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

Mat = [[float('inf')] * (N - 1) + [N] for d in range(20)]
prev = [-1] * 20

for i, A in enumerate(As):
    binA = format(A, 'b').zfill(20)
    for d in range(20):
        if binA[d] == '1':
            if prev[d] != -1:
                Mat[d][prev[d]] = i
            prev[d] = i

minM = list(map(min, *Mat))

for i in reversed(range(N - 1)):
    minM[i] = min(minM[i], minM[i + 1])

print(sum(minM) - N * (N - 1) // 2)
Buggy python submission (verdict: Time Limit Exceeded):
N, K, Q = map(int, input().split())
As = list(map(int, input().split()))

ans = 10 ** 9
for Y in As:
    cands = []
    cs = []
    for A in As + [0]: # 最終要素は番兵
        if A < Y:
            cands += sorted(cs)[:max(0, len(cs) - K + 1)]
            cs = []
        else:
            cs += [A]

    if len(cands) < Q: continue
    X = sorted(cands)[Q - 1]

    ans = min(ans, X - Y)

print(ans)


Fixed submission:
N, K, Q = map(int, input().split())
As = list(map(int, input().split()))

ans = 10 ** 9
for Y in sorted(As)[:N - Q - K + 2]:
    cands = []
    cs = []
    for A in As + [0]: # 最終要素は番兵
        if A < Y:
            if len(cs) >= K:
                cands += sorted(cs)[:len(cs) - K + 1]
            cs = []
        else:
            cs += [A]

    if len(cands) < Q: continue
    X = sorted(cands)[Q - 1]

    ans = min(ans, X - Y)

print(ans)
Buggy python submission (verdict: Runtime Error):
import math

Q = int(input())
ABs = [list(map(int, input().split())) for i in range(Q)]

for A, B in ABs:
    n = math.floor(math.sqrt(A * B - 1))
    ans = 2 * n

    if (A * B - 1) // n == n:
        ans -= 1
    if A <= n:
        ans -= 1
    if B <= n - 1:
        ans -= 1

    print(ans)



Fixed submission:
Q = int(input())
querys = [tuple(map(int, input().split())) for _ in range(Q)]

anss = []
for A, B in querys:
    if A > B:
        A, B = B, A

    if A == B:
        ans = 2*(A-1)
    elif A+1 == B:
        ans = 2*(A-1)
    else:
        C = -(-((A*B)**0.5) // 1) - 1
        if C*(C+1) >= A*B:
            ans = 2*(C-1)
        else:
            ans = 2*C-1

    anss.append(int(ans))

print('\n'.join(map(str, anss)))
Buggy python submission (verdict: Runtime Error):
N, A, B = map(int, input().split())

if A + B > N + 1:
    print('-1')
else:
    ans = list(range(N - B + 1, N + 1)[::-1])
    Ns = list(range(1, N - B + 1))
    for i in range((N - B) // (A - 1) + 1):
        st = i * (A - 1)
        ans = Ns[st:st + A - 1] + ans
    print(ans)


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

if A + B - 1 > N or A * B < N:
    print('-1')
else:
    ans = list(range(1, B + 1)[::-1])
    if A > 1:
        x = (N - B) // (A - 1)
        y = (N - B) % (A - 1)
        st = B + 1
        for i in range(y):
            ans += list(range(st, st + x + 1)[::-1])
            st += x + 1
        for i in range(A - 1 - y):
            ans += list(range(st, st + x)[::-1])
            st += x

    print(' '.join(map(str, ans)))
Buggy python submission (verdict: Time Limit Exceeded):
H, W, D = map(int, input().split())
As = [list(map(int, input().split())) for i in range(H)]
Q = int(input())
LRs = [list(map(int, input().split())) for i in range(Q)]

poss = [(0, 0)] * (H * W)
for i in range(H):
    for j in range(W):
        poss[As[i][j] - 1] = (i, j)

for L, R in LRs:
    ans = 0
    pi, pj = poss[L - 1]
    for i, j in poss[L - 1 + D:R + 1:D]:
        ans += abs(i - pi) + abs(j - pj)
        pi, pj = i, j
    print(ans)


Fixed submission:
H, W, D = map(int, input().split())
As = [list(map(int, input().split())) for i in range(H)]
Q = int(input())
LRs = [list(map(int, input().split())) for i in range(Q)]

poss = [(0, 0)] * (H * W)
for i in range(H):
    for j in range(W):
        poss[As[i][j] - 1] = (i, j)

MPs = [[] for i in range(D)]
for st in range(1, D + 1):
    MPs[st - 1] += [0]
    pi, pj = poss[st - 1]
    for i, j in poss[st - 1 + D::D]:
        MPs[st - 1] += [MPs[st - 1][-1] + abs(i - pi) + abs(j - pj)]
        pi, pj = i, j

for L, R in LRs:
    st = (L - 1) % D + 1
    print(MPs[st - 1][(R - st) // D] - MPs[st - 1][(L - st) // D])
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate
from operator import add

N, K = map(int, input().split())
K2 = 2 * K

# Gss[i][j]: 「市松模様の黒い部分の右上のマス」が(i,j)のとき、満たせる要望の個数
Gss = [[0] * K2 for i in range(K2)]

for i in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)

    # 要望を「0<=x<2K, 0<=y<K, 'B'」に変換する
    if c == 'W':
        x -= K
    x, y = x % K2, y % K2

    if y >= K:
        x, y = (x - K) % K2, y - K

    # 要望を満たす「市松模様の黒い部分の右上のマス」に対して、+1する
    # （後で累積和を取る）
    Gss[x][y] += 1
    Gss[x][y - K] += -1
    if x != K:
        Gss[x - K][y - K] += 1
        Gss[x - K][y] += -1
    if x > K:
        Gss[0][y] += 1
        Gss[0][y - K] += -1

# 累積和を取る
Gss = [list(accumulate(Gs)) for Gs in Gss]
Gss = [list(accumulate(Gs)) for Gs in zip(*Gss)]
Gss = list(map(list, zip(*Gss))) # 転置

# 「K<=y<2K」の部分を、「0<=y<K」に重ね合わせる
Gss = [list(map(add, Gss[i][:K], Gss[i - K][K:])) for i in range(K2)]

# Gssの最大値が答え
print(max(map(max, Gss)))


Fixed submission:
from operator import sub

N, K = map(int, input().split())

numA = [[0] * K for i in range(K)]
numB = [[0] * K for i in range(K)]

for i in range(N):
    x, y, c = input().split()
    x = int(x) % (2 * K)
    y = int(y) % (2 * K)

    if c == 'B':
        if (x // K == 0 and y // K == 0) or (x // K == 1 and y // K == 1):
            numA[x % K][y % K] += 1
        else:
            numB[x % K][y % K] += 1
    else:
        if (x // K == 1 and y // K == 0) or (x // K == 0 and y // K == 1):
            numA[x % K][y % K] += 1
        else:
            numB[x % K][y % K] += 1


sumXA = list(map(sum, numA))
sumYA = list(map(sum, zip(*numA)))

sumXB = list(map(sum, numB))
sumYB = list(map(sum, zip(*numB)))

sumA = sum(sumXA)
sumB = sum(sumXB)

Arr = [[0] * K for i in range(K)]
numOKA = sumA
numOKB = sumB
for x in range(K):

    tempOKA = numOKA
    tempOKB = numOKB
    for y in range(K):
        Arr[x][y] = max(tempOKA + sumB - tempOKB, sumA - tempOKA + tempOKB)
        tempOKA -= sumYA[y]
        tempOKB -= sumYB[y]

    sumYA = list(map(sub, sumYA, numA[x]))
    sumYA = list(map(sub, sumYA, numA[x]))
    numOKA -= sumXA[x]

    sumYB = list(map(sub, sumYB, numB[x]))
    sumYB = list(map(sub, sumYB, numB[x]))
    numOKB -= sumXB[x]

print(max(map(max, Arr)))
Buggy python submission (verdict: Runtime Error):
from math import ceil, floor

K = int(input())
As = list(map(int, input().split()))

L = 2
R = 2
for A in reversed(As):
    if R // A * A < L:
        print('-1')
        exit()
    L = ceil(L / A) * A
    R = floor(R / A) * A + A - 1

print(L, R)


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

if (B - A) % 2 == 0:
    print('Alice')
else:
    print('Borys')
Buggy python submission (verdict: Time Limit Exceeded):
from math import ceil, sqrt

Q = int(input())
querys = [tuple(map(int, input().split())) for i in range(Q)]

N = max(map(max, querys))

Primes = [False] * 2 + [True] * (N - 1)
for i in range(3, N + 1):
    for j in range(2, ceil(sqrt(i)) + 1):
        if i % j == 0:
            Primes[i] = False

s2017s = [False] * (N + 1)
for i in range(1, N + 1, 2):
    if Primes[i] and Primes[(i + 1) // 2]:
        s2017s[i] = True

nums = [0] * (N + 1)
for i in range(1, N + 1, 2):
    nums[i] = nums[i - 2]
    if s2017s[i]:
        nums[i] += 1

for li, ri in querys:
    print(nums[ri] - nums[max(0, li - 2)])


Fixed submission:
from math import ceil, sqrt

Q = int(input())
querys = [tuple(map(int, input().split())) for i in range(Q)]

N = max(map(max, querys))

Primes = [False] * 2 + [True] * (N - 1)
for i in range(3, N + 1):
    for j in range(2, ceil(sqrt(i)) + 1):
        if i % j == 0:
            Primes[i] = False
            break

s2017s = [False] * (N + 1)
for i in range(1, N + 1, 2):
    if Primes[i] and Primes[(i + 1) // 2]:
        s2017s[i] = True

nums = [0] * (N + 1)
for i in range(1, N + 1, 2):
    nums[i] = nums[i - 2]
    if s2017s[i]:
        nums[i] += 1

for li, ri in querys:
    print(nums[ri] - nums[max(0, li - 2)])
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
x, y = map(int, input().split())

s2 = s.split('T')
sXs = list(map(len, s2[0::2]))
sYs = list(map(len, s2[1::2]))

memoX = [{sXs[0]}, set()]
for i, sX in enumerate(sXs[1:]):
    memoX[1 - i % 2] = set()
    for p in memoX[i % 2]:
        memoX[1 - i % 2].add(p + sX)
        memoX[1 - i % 2].add(p - sX)

memoY = [{0}, set()]
for i, sY in enumerate(sYs):
    memoY[1 - i % 2] = set()
    for p in memoY[i % 2]:
        memoY[1 - i % 2].add(p + sY)
        memoY[1 - i % 2].add(p - sY)

if x in memoX[1 - len(sXs) % 2] and y in memoY[len(sYs) % 2]:
    print('Yes')
else:
    print('No')


Fixed submission:
s = input()
x, y = map(int, input().split())

s2 = s.split('T')
sXs = list(map(len, s2[0::2]))
sYs = list(map(len, s2[1::2]))

memoX = [{sXs[0]}, set()]
for i, sX in enumerate(sXs[1:]):
    memoX[1 - i % 2] = set()
    for p in memoX[i % 2]:
        memoX[1 - i % 2].add(p + sX)
        memoX[1 - i % 2].add(p - sX)

memoY = [{0}, set()]
for i, sY in enumerate(sYs):
    memoY[1 - i % 2] = set()
    for p in memoY[i % 2]:
        memoY[1 - i % 2].add(p + sY)
        memoY[1 - i % 2].add(p - sY)

if x in memoX[1 - len(sXs) % 2] and y in memoY[len(sYs) % 2]:
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Time Limit Exceeded):
N, C = map(int, input().split())
TVs = [[] for i in range(C)]
for i in range(N):
    s, t, c = map(int, input().split())
    TVs[c - 1].append((s, t))

periods = [0] * (2 * 10 ** 5)

for c, TVc in enumerate(TVs):
    ps = [0] * (2 * 10 ** 5)

    for s, t in TVc:
        ps[s * 2 - 1: t * 2 - 2 + 1] = list(map(lambda x: x + 1, ps[s * 2 - 1: t * 2 - 2 + 1]))

    for i in range(len(ps) - 1):
        ps[i] = max(ps[i], ps[i + 1])

    periods = list(map(sum, zip(periods, ps)))

print(max(periods))


Fixed submission:
import heapq

N, C = map(int, input().split())
TVs = [[] for i in range(C)]
for i in range(N):
    s, t, ch = map(int, input().split())
    TVs[ch - 1].append((s, t))

pq = []
for ch, TVc in enumerate(TVs):
    if not TVc: continue
    TVc.sort()
    heapq.heappush(pq, (TVc[0][0] - 0.5, ch))

states = [0] * C
iTVs = [0] * C

prev = 0
ans = 0
while pq:
    tm, ch = heapq.heappop(pq)
    if tm != prev:
        ans = max(ans, sum(states))
        prev = tm

    if states[ch] == 0:
        # チャンネルchの番組録画を、時刻tmから開始
        states[ch] = 1
        heapq.heappush(pq, (TVs[ch][iTVs[ch]][1], ch)) # 終了時刻をpqに追加
    else:
        # チャンネルchの番組録画を、時刻tmで終了
        states[ch] = 0
        iTVs[ch] += 1
        if iTVs[ch] >= len(TVs[ch]): continue

        if tm == TVs[ch][iTVs[ch]][0]:
            # 録画範囲が連続しているならば、次の番組録画を開始
            states[ch] = 1
            heapq.heappush(pq, (TVs[ch][iTVs[ch]][1], ch)) # 終了時刻をpqに追加
        else:
            heapq.heappush(pq, (TVs[ch][iTVs[ch]][0] - 0.5, ch)) # 次の開始時刻をpqに追加

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

def solve():
    N, Q = map(int, input().split())

    anss = []
    for _ in range(Q):
        v, w = map(int, input().split())
        v, w = v-1, w-1
        while v != w:
            if v > w:
                v = (v-1)//N
            else:
                w = (w-1)//N
        anss.append(v + 1)

    print('\n'.join(map(str, anss)))

solve()


Fixed submission:
N, Q = map(int, input().split())
vws = [tuple(map(int, input().split())) for _ in range(Q)]

anss = []
if N == 1:
    anss = [min(v, w) for v, w in vws]
else:
    for v, w in vws:
        v, w = v-1, w-1
        while v != w:
            if v > w:
                v = (v-1)//N
            else:
                w = (w-1)//N
        anss.append(v + 1)

print('\n'.join(map(str, anss)))

Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split())
vws = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(Q)]

anss = []
for v, w in vws:
    while v != w:
        if v > w:
            v = (v-1)//N
        else:
            w = (w-1)//N
    anss.append(v + 1)

print('\n'.join(map(str, anss)))


Fixed submission:
N, Q = map(int, input().split())
vws = [tuple(map(int, input().split())) for _ in range(Q)]

anss = []
if N == 1:
    anss = [min(v, w) for v, w in vws]
else:
    for v, w in vws:
        v, w = v-1, w-1
        while v != w:
            if v > w:
                v = (v-1)//N
            else:
                w = (w-1)//N
        anss.append(v + 1)

print('\n'.join(map(str, anss)))

Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split())
vws = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(Q)]

anss = []
for v, w in vws:
    parVs, parWs = set(), set()
    while v >= 0:
        parVs.add(v)
        v = (v-1)//N
    while w >= 0:
        parWs.add(w)
        w = (w-1)//N
    anss.append(max(parVs & parWs) + 1)

print('\n'.join(map(str, anss)))


Fixed submission:
N, Q = map(int, input().split())
vws = [tuple(map(int, input().split())) for _ in range(Q)]

anss = []
if N == 1:
    anss = [min(v, w) for v, w in vws]
else:
    for v, w in vws:
        v, w = v-1, w-1
        while v != w:
            if v > w:
                v = (v-1)//N
            else:
                w = (w-1)//N
        anss.append(v + 1)

print('\n'.join(map(str, anss)))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter

N = int(input())

cntA = Counter(map(int, input().split()))
cntB = Counter(map(int, input().split()))
cntC = Counter(map(int, input().split()))

keyA = sorted(list(cntA.keys()))
keyB = sorted(list(cntB.keys()))
keyC = sorted(list(cntC.keys()))

iA = 0
iC = 0
numA = 0
numC = N
ans = 0
for kB in keyB:
    for i, k in enumerate(keyA[iA:], iA):
        if k >= kB:
            iA = i
            break
        numA += cntA[k]
    else:
        iA = len(keyA)

    for i, k in enumerate(keyC[iC:], iC):
        if k > kB:
            iC = i
            break
        numC -= cntC[k]
    else:
        iC = len(keyC)

    ans += numA * numC * cntB[kB]

print(ans)


Fixed submission:
from collections import Counter

N = int(input())

cntA = Counter(map(int, input().split()))
cntB = Counter(map(int, input().split()))
cntC = Counter(map(int, input().split()))

keyA = sorted(list(cntA.keys()))
keyB = sorted(list(cntB.keys()))
keyC = sorted(list(cntC.keys()))

lenA = len(keyA)
lenC = len(keyC)
iA = 0
iC = 0
numA = 0
numC = N
ans = 0
for kB in keyB:
    for i in range(iA, lenA):
        if keyA[i] >= kB:
            iA = i
            break
        numA += cntA[keyA[i]]
    else:
        iA = lenA

    for i in range(iC, lenC):
        if keyC[i] > kB:
            iC = i
            break
        numC -= cntC[keyC[i]]
    else:
        iC = lenC

    ans += numA * numC * cntB[kB]

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate

N = int(input())
ts = list(map(int, input().split()))
vs = list(map(int, input().split()))

# 各区間の制限速度条件のみを満たす最大速度のグラフを求める
accTs = list(accumulate(ts))
sumT = accTs[-1]
vMaxs = [100] * (2 * sumT + 1)
for v, l, r in zip(vs + [0, 0], [0] + accTs[:-1] + [0, sumT], accTs + [0, sumT]):
    vms = []
    for t2 in range(sumT * 2 + 1):
        t = t2 / 2
        if t <= l:
            vms += [v + l - t]
        elif t <= r:
            vms += [v]
        else:
            vms += [v + t - r]

    # 最小値がその時刻における列車の速度になる
    vMaxs = list(map(min, vMaxs, vms))

print(sum(vMaxs) / 2)



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

sumT = sum(ts)
va = [min(i / 2, sumT - i / 2) for i in range(2 * sumT + 1)]

accT = 0
for t, v in zip(ts, vs):
    for i in range(accT, accT + 2 * t + 1):
        va[i] = min(va[i], v)
    accT += t * 2

for i in range(len(va) - 1):
    if va[i + 1] - va[i] > 0.5:
        va[i + 1] = va[i] + 0.5

for i in range(len(va) - 1)[::-1]:
    if va[i] - va[i + 1] > 0.5:
        va[i] = va[i + 1] + 0.5

print(sum(va) / 2)
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
adjL = [[] for v in range(N)]
for e in range(M):
    A, B = map(int, input().split())
    adjL[A - 1].append(B - 1)
    adjL[B - 1].append(A - 1)

# 二部グラフかどうかを判定する（頂点を1or-1で塗っていく）
colors = [0] * N

def dfs(vNow, color):
    colors[vNow] = color # 頂点vNowをcolorで塗る
    for v in adjL[vNow]:
        if colors[v] == color:
            # 隣接する頂点vが同じ色で彩色済みならば、二部グラフではない
            return False
        if colors[v] == 0 and not dfs(v, -color):
            # 隣接する頂点vが未彩色ならば、もう１つの色で塗ってみる
            return False

    return True


IsBipartite = dfs(0, 1)

if IsBipartite:
    # 二部グラフである場合
    num = colors.count(1)
    print(num * (N - num) - M)
else:
    # 二部グラフでない場合
    print(N * (N - 1) // 2 - M)


Fixed submission:
import sys
sys.setrecursionlimit(10 ** 6)

N, M = map(int, input().split())
adjL = [[] for v in range(N)]
for e in range(M):
    A, B = map(int, input().split())
    adjL[A - 1].append(B - 1)
    adjL[B - 1].append(A - 1)

# 二部グラフかどうかを判定する（頂点を1or-1で塗っていく）
colors = [0] * N

def dfs(vNow, color):
    colors[vNow] = color # 頂点vNowをcolorで塗る
    for v in adjL[vNow]:
        if colors[v] == color:
            # 隣接する頂点vが同じ色で彩色済みならば、二部グラフではない
            return False
        if colors[v] == 0 and not dfs(v, -color):
            # 隣接する頂点vが未彩色ならば、もう１つの色で塗ってみる
            return False

    return True


IsBipartite = dfs(0, 1)

if IsBipartite:
    # 二部グラフである場合
    num = colors.count(1)
    print(num * (N - num) - M)
else:
    # 二部グラフでない場合
    print(N * (N - 1) // 2 - M)
Buggy python submission (verdict: Runtime Error):
N = int(input())
s = input()

while s.count('000'):
    s = s.replace('000', '00')
ss = s.split('00')

A = []
for si in ss:
    num = 0
    ai = []
    for c in si:
        if c == '1':
            num += 1
        else:
            if num > 0:
                ai.append(num)
                num = 0

    if num > 0:
        ai.append(num)

    A.append(ai)

ans = 0
for ai in A:
    if ai[0] < ai[-1]:
        ai = ai[::-1]

    flg = True
    for i, aa in enumerate(ai):
        if i == len(ai) - 1:
            break

        if flg == True:
            ans += aa
            flg = False
        else:
            ans += aa - 1
            if aa == 1:
                flg = True

print(ans)


Fixed submission:
N = int(input())
s = input()

# 「連続する1の数」のリストに変換する
s = s[s.find('1'):] # 先頭の'0'を取り除く
while s.count('000'):
    s = s.replace('000', '00')
cs = list(map(len, s.split('0')))

# dp[i]: i番目の「連続する1」への各処理（操作に使わない／左の１つだけ使う／右の１つを残して使う／全て使う）
#        に対して、現時点での操作回数の最大値
dp = [[-float('inf')] * 4 for i in range(len(cs))]
dp[0][0] = 0
for i in range(1, len(cs)):
    if cs[i] == 0:
        dp[i][3] = max(dp[i - 1])
        continue

    # 使わない
    dp[i][0] = max(dp[i - 1])
    # 全て使う
    dp[i][3] = max(dp[i - 1][0] + max(cs[i - 1], cs[i]), \
                   dp[i - 1][1] + max(cs[i - 1] - 1, cs[i]), \
                   dp[i - 1][2] + cs[i], \
                   dp[i - 1][3])
    if cs[i] >= 2:
        # 左の１つだけ使う
        dp[i][1] = max(dp[i - 1][0] + cs[i - 1], \
                       dp[i - 1][1] + cs[i - 1] - 1, \
                       dp[i - 1][2] + 1, \
                       dp[i - 1][3])
        # 右の１つを残して使う
        dp[i][2] = max(dp[i - 1][0] + max(cs[i - 1], cs[i] - 1), \
                       dp[i - 1][1] + max(cs[i - 1] - 1, cs[i] - 1), \
                       dp[i - 1][2] + cs[i] - 1, \
                       dp[i - 1][3])

print(max(dp[-1]))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
a = list(map(int, input().split()))

num = [0 for i in range(3)]
num[0] = a.count(0)
num[1] = a.count(1)

ans = 0
for X in range(1, 100000):
    num[(X % 3) - 2] = a.count(X + 1)
    ans = max(ans, sum(num))

print(ans)


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

num = [0 for i in range(100000)]
for aa in a:
    num[aa] += 1

ans = 0
for X in range(1, 99999):
    ans = max(ans, sum(num[X-1:X+2]))

print(ans)