Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p02716 (python)

Fixed submission:
# coding: utf-8
import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 9)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()
# 奇数の時と偶数の時、奇数の場合は真ん中を選ぶかどうか
INF = 10 ** 17

@lru_cache(None)
def F(index, n):
    if index >= N:
        return -INF
    if N - index + 2 < 2 * n:
        return -INF
    if n == 0:
        return 0
    elif n == 1:
        return max(A[index:])
    ret = max(A[index] + F(index+2, n-1), F(index+1, n))
    return ret

answer = F(0, N//2)
print(answer)

Buggy submission (verdict: Runtime Error):
# coding: utf-8
import sys
from functools import lru_cache

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()
# 奇数の時と偶数の時、奇数の場合は真ん中を選ぶかどうか
INF = 10 ** 17

@lru_cache(None)
def F(index, n):
    if index >= N:
        return -INF
    if n == 0:
        return 0
    elif n == 1:
        return max(A[index:])
    ret = max(A[index] + F(index+2, n-1), F(index+1, n))
    return ret

answer = F(0, N//2)
print(answer)
Problem p02732 (python)

Fixed submission:
import sys
from collections import Counter

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()
counter = Counter(A)
total = sum(x*(x-1)//2 for x in counter.values())
for a in A:
    x = counter[a]
    temp = total
    temp -= x * (x-1) // 2
    if x > 2:
        temp += (x-1) * (x-2) // 2
    print(temp)

Buggy submission (verdict: Runtime Error):
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = np.array(lr(), dtype=np.int32)
counter = np.bincount(A)
case = (counter * (counter-1) // 2).sum()
answer = case - (counter[A] - 1)
print('\n'.join(map(str, answer)))
Problem p02768 (python)

Fixed submission:
import sys
from functools import reduce

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, A, B = lr()
MOD = 10 ** 9 + 7

def F(A):
    num = reduce(lambda x, y: x * y % MOD, range(N, N-A, -1))
    den = reduce(lambda x, y: x * y % MOD, range(1, A+1))
    return num * pow(den, MOD-2, MOD) % MOD

answer = pow(2, N, MOD) - F(A) - F(B) - 1
print(answer % MOD)

Buggy submission (verdict: Runtime Error):
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, A, B = lr()
MOD = 10 ** 9 + 7

def cmb(n, k):
    if k > n:
        return 0
    return fact[n] * fact_inv[k] % MOD * fact_inv[n-k] % MOD

def cumprod(arr, MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]; arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv

def power_func(a,n,p):
    bi=str(format(n,"b"))#2進表現に
    res=1
    for i in range(len(bi)):
        res=(res*res) %p
        if bi[i]=="1":
            res=(res*a) %p
    return res

U = N+1 # 階乗テーブルの上限
fact, fact_inv = make_fact(U, MOD)
answer = power_func(2, N, MOD) - 1 - cmb(N, A) - cmb(N, B)
print(answer%MOD)
Problem p02780 (python)

Fixed submission:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
P = np.array([0] + lr())
P = (P+1) / 2
Pcum = P.cumsum()
X = Pcum[K:] - Pcum[:-K]
answer = X.max()
print(answer)

Buggy submission (verdict: Runtime Error):
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
P = np.array(lr(), np.float64)
P += 1; P /= 2
P = [0] + P
Pcum = P.cumsum()
expectation = Pcum[K:] - Pcum[:-K]
answer = expectation.max()
print(answer)

Buggy submission (verdict: Runtime Error):
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
P = np.array(lr(), np.float32)
P += 1; P /= 2
P = [0] + P
Pcum = P.cumsum()
expectation = Pcum[K:] - Pcum[:-K]
answer = expectation.max()
print(answer)

Buggy submission (verdict: Runtime Error):
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
P = np.array(lr(), np.float32)
P += 1; P /= 2
P = [0] + P
print(P)
Pcum = P.cumsum()
expectation = Pcum[K:] - Pcum[:-K]
answer = expectation.max()
print(answer)
Problem p02788 (python)

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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, D, A = lr()
XH = [lr() for _ in range(N)]
XH.sort()

over = [N] * N # over[i]はi番目のモンスターを攻撃した時影響のないモンスターの最小値（最大はNで対象なし）
cur = 1
for i in range(N):
    while cur < N and XH[i][0] + D + D >= XH[cur][0]:
        cur += 1
    over[i] = cur

damage = 0 # 今までの累計のダメージ数　(影響のないダメージは引く)
reset = [0] * (N+1) # これ以降関係のないダメージ
answer = 0
for i in range(N):
    x, h = XH[i]
    damage -= reset[i]
    h -= damage
    if h > 0:
        time = (h+A-1)//A
        answer += time
        damage += A * time
        reset[over[i]] += A * time

print(answer)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, D, A = lr()
XH = [lr() for _ in range(N)]
XH.sort(key=lambda x:x[0])

over = [N] * (N+1) # over[i]はi番目のモンスターを攻撃した時影響のないモンスターの最小値（最大はNで対象なし）
cur = 1
for i in range(N):
    while cur <= N and XH[i][0] + D + D >= XH[cur][0]:
        cur += 1
    over[i] = cur

damage = 0 # 今までの累計のダメージ数　(影響のないダメージは引く)
reset = [0] * (N+1) # 対象のモンスターの影響しなかったダメージ
answer = 0
for i in range(N):
    x, h = XH[i]
    damage -= reset[i]
    h = h - damage
    time = (h+A-1)//A
    answer += time
    damage += A * time
    reset[over[i]] += A * time

print(answer)
# 00
Problem p02802 (python)

Fixed submission:
import sys
#import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, M = rl()
solve = [False] * (N+1)
count = [0] * (N+1)
penalty = 0
for i in range(M):
    p, s = input().split()
    p = int(p)
    if solve[p]:
        continue
    if s == 'WA':
        count[p] += 1
    else:
        solve[p] = True
        penalty += count[p]

print(sum(solve), penalty)

Buggy submission (verdict: Runtime Error):
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
problems = [False] * N
AC = [0] * N
WA = [0] * N
for _ in range(M):
    p, S = sr().split(); p = int(p) - 1
    if not problems[p] and S == 'WA':
        WA[p] += 1
    if not problems[p] and S == 'AC':
        problems[p] = True
        AC += 1

AC_total = sum(AC)
WA_total = sum(y for x, y in zip(AC, WA) if x)
print(AC_total, WA_total)
Problem p02804 (python)

Fixed submission:
import sys
from math import factorial
import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

def cumprod(arr, MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]; arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv

U = 10**6
MOD = 10 ** 9 + 7
fact, fact_inv = make_fact(U, MOD)
N, K = rl()
A = rl()
A.sort()
min = A[0]
A = [(x - min)%MOD for x in A]
#最大値として何回登場するか
count = 0

for i in range(K-1, N):
    # A[i] * iC(k-1)
    count += A[i] * fact[i] % MOD * fact_inv[K-1] % MOD * fact_inv[i-(K-1)] % MOD
    count %= MOD
for i in range(N-K+1):
    # A[i] * (N-(i+1)) C (k-1)
    count -= A[i] * fact[N-(i+1)] % MOD * fact_inv[K-1] % MOD * fact_inv[N-(i+1)-(K-1)] % MOD
    count %= MOD

print(count)

Buggy submission (verdict: Runtime Error):
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7

# 組合せ nCr (MOD) 逆元を使う方法
def perm(n,k):
    if k > n or k < 0: return 0
    return fact[n] * fact_inv[n-k] % MOD

def cmb(n, k):
    if k < 0 or k > n: return 0 
    return fact[n] * fact_inv[k] % MOD * fact_inv[n-k] % MOD

def cumprod(arr, MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]; arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv

U = 10 ** 5 + 100 # 階乗テーブルの上限
fact, fact_inv = make_fact(U, MOD)
N, K = lr()
A = np.array(lr())
A.sort()
coef = np.zeros(N, np.int64)
coef[K-1:] = [cmb(n, K-1) for n in range(K-1, N)]
answer = (A * coef % MOD).sum() % MOD
coef = np.zeros(N, np.int64)
coef[:-K+1] = [cmb(n, K-1) for n in range(N-1, K-2, -1)]
answer -= (A * coef % MOD).sum() % MOD
print(answer%MOD)
# 53
Problem p02807 (python)

Fixed submission:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def cumprod(arr, MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]; arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv

MOD = 10 ** 9 + 7
U = 10 ** 5 + 10 # 階乗テーブルの上限
fact, fact_inv = make_fact(U, MOD)
N = ir()
X = np.array(lr())

inv = np.zeros(U, np.int64)
inv[1:] = fact_inv[1:] * fact[:-1] % MOD
coef = inv[1:N].cumsum() % MOD
answer = (np.diff(X) * coef % MOD).sum() % MOD
answer *= fact[N-1]
print(answer % MOD)
# 35

Buggy submission (verdict: Runtime Error):
import sys
import math
#import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
X = rl()
MOD = 10 ** 9 + 7
limit = math.factorial(N-1)
last = X[-1]
X = [last - x for x in X] #最後までの距離
answer = 0
for i in range(1, N):
    answer += (X[i-1] * limit / i)%MOD
    answer %= MOD

print(answer)
Problem p02814 (python)

Fixed submission:
import sys
import numpy as np
from fractions import gcd
from functools import reduce

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, M = rl()
A = np.array(rl())
B = A // 2

def merge(a, b):
    g = gcd(a, b)
    a //= g; b //= g
    if a%2 == 0 or b%2 == 0:
        return 0
    n = g * a * b
    if n > 10 ** 9:
        return 0
    return n

x = reduce(merge, B)
if x == 0:
    answer = 0
else:
    answer = M // x - M // (2*x)

print(answer)

Buggy submission (verdict: Runtime Error):
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# A が2で何回割れるか
N, M = lr()
A = lr()
A = [x // 2 for x in A]
cnt = 0
while all(x%2 == 0 for x in A):
    cnt += 1
    A = [x // 2 for x in A]

if any(x%2 == 0 for x in A):
    print(0); exit()
lcm = 1
for a in A:
    lcm *= a // gcd(lcm, a)

answer = M // lcm - M // (2 * lcm)
print(answer)
# 21
Problem p02838 (python)

Fixed submission:
import sys
import numpy as np

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
A = np.array(rl())
answer = 0
MOD = 10 ** 9 + 7

for n in range(63):
    B = (A >> n) & 1
    x = np.count_nonzero(B)
    y = N - x
    x *= y
    for _ in range(n):
        x *= 2
        x %= MOD
    answer += x

print(answer%MOD)

Buggy submission (verdict: Runtime Error):
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
N = ir()
A = np.array(lr(), np.int64)
answer = 0
limit = A.max().bit_length()
for i in range(limit):
    B = (A >> i) & 1
    x = np.count_nonzero(B)
    y = N - x
    add = (x*y) * 2 ** i % MOD
    answer += add

print(answer%MOD)
Problem p02845 (python)

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

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

color = [0] * 3 # 赤色・青色・緑色の帽子を被っている人数
answer = 1 
MOD = 10 ** 9 + 7

for a in A:
    if color.count(a) == 0:
        print(0)
        exit()
    answer *= color.count(a)
    # aと同じ人数が複数ある場合は一番左の色としてカウント
    i = color.index(a)
    color[i] += 1
    answer %= MOD

print(answer)

Buggy submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))
color = [0] * 3 # 赤色・青色・緑色の帽子を被っている人数
answer = 1 
MOD = 10 ** 9 + 7

for a in A:
    answer *= color.count(a)
    # aと同じ人数が複数ある場合は一番左の色としてカウント
    i = color.index(a)
    color[i] += 1
    answer %= MOD

print(answer)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10 ** 7)

N = int(input())
A = list(map(int, input().split()))
color = [0] * 3 # 赤色・青色・緑色の帽子を被っている人数
answer = 1 
MOD = 10 ** 9 + 7

for a in A:
    answer *= color.count(a)
    # aと同じ人数が複数ある場合は一番左の色としてカウント
    i = color.index(a)
    color[i] += 1
    answer %= MOD

print(answer)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10 ** 9)

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
A = rl()
color = [0] * 3
answer = 1
MOD = 10 ** 9 + 7

for a in A:
    answer = answer * color.count(a) % MOD
    i = color.index(a)
    color[i] += 1
    if answer == 0:
        break

print(answer)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10 ** 9)

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
A = rl()
color = [0] * 3
answer = 1
MOD = 10 ** 9 + 7

for a in A:
    answer *= color.count(a)
    i = color.index(a)
    color[i] += 1

print(answer%MOD)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10 ** 9)

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
A = rl()
color = [0] * 3
answer = 1
MOD = 10 ** 9 + 7

for a in A:
    answer *= color.count(a)
    i = color.index(a)
    color[i] += 1
    answer %= MOD

print(answer)
Problem p02868 (python)

Fixed submission:
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def dijkstra(start):
    dist = [INF] * (N+1)
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, prev = heappop(que)
        if dist[prev] < d:
            continue
        for cost, next in graph[prev]:
            d1 = d + cost
            if dist[next] > d1:
                dist[next] = d1
                heappush(que, (d1, next))
    return dist

N, M = lr()
INF = 10 ** 15
graph = [[] for _ in range(N+1)] # 1-indexed
for i in range(2, N+1):
    graph[i].append((0, i-1))

for _ in range(M):
    l, r, c = lr()
    graph[l].append((c, r))

dist = dijkstra(1)

if dist[N] == INF:
    print(-1)
else:
    print(dist[N])
# 19

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
LRC = [list(map(int, input().split())) for _ in range(M)]
INF = 10 ** 10
LRC.sort(key=lambda x: x[2], reverse=True)
LRC.sort()
dp = [INF] * (N+1) # dp[0]は使わない
dp[1] = 0
for l, r, c in LRC:
    x = dp[l] + c
    for i in range(r+1, l-1, -1):
        if dp[i] > x:
            dp[i] = x
        else:
            break
if dp[N] == INF:
    print(-1)
else:
    print(dp[N])

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
LRC = [list(map(int, input().split())) for _ in range(M)]
INF = 10 ** 10
for i in range(N+1):
    graph[i][i] = 0
LRC.sort(key=lambda x: x[2], reverse=True)
LRC.sort()
dp = [INF] * (N+1) # dp[0]は使わない
visited = 1
dp[1] = 0
for l, r, c in LRC:
    if l > visited:
        print(-1)
        exit()
    if r > visited:
        visited = r
    x = dp[l] + c
    dp[r] = min(dp[r], x)
if dp[N] == INF:
    print(-1)
else:
    print(dp[N])
Problem p02874 (python)

Fixed submission:
import sys

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))  # applies to only numbers
rs = lambda: stdin.readline().rstrip()  # ignores trailing space

N = ri()
L = []
R = []

for _ in range(N):
    l, r = rl()
    L.append(l)
    R.append(r)

max_l = max(L)
min_r = min(R)
ab = [(max(0, r - max_l + 1), max(0, min_r - l + 1)) for l, r in zip(L, R)]
ab.sort()
mi = float('inf')
answer = max(r - l + 1 for l, r in zip(L, R)) + max(0, min_r - max_l + 1)
for i in range(N - 1):
    mi = min(mi, ab[i][1])
    # miは第１グループの人数
    answer = max(answer, mi + ab[i + 1][0])
print(answer)

Buggy submission (verdict: Runtime Error):
# 一番長いLRが最低の楽しさ
# 一番長いLRと重なるのが一番少ないものはもう一つにする
# 一番長いLRが最低の楽しさ 一番長いLRが複数ある場合どうする？
# 一番長いLRと重なるのが一番少ないものはもう一つにする
N = int(input())
LR = [list(map(int, input().split())) for _ in range(N)][::-1]
LR.sort(key=lambda x: x[1]-x[0], reverse=True)
ma = LR[0][1] - LR[0][0] + 1
left_ma = LR[0][0]
right_ma = LR[0][1]

ma2 = ma
another = 10 ** 9
another_length = 0 #重なっていない長さ
LR.pop(0)

another_length = LR[1][1] - LR[1][0] + 1
left_an = LR[1][0]
right_an = LR[1][1]

point = ma + another_length
LR.pop(1)
for l, r in LR:
    if max(0, min(right_ma, r) - max(left_ma, l)) + another_length < ma + max(0, min(right_an, r) - max(left_an, l)):
        # anotherのグループにいれる
        another_length = max(0, min(right_an, r) - max(left_an, l) + 1)
        point = ma + another_length
        right_an = min(r, right_an)
        left_an = max(l, left_an)
        #print(right_an, left_an)
    else:
        ma = max(0, min(right_ma, r) - max(left_ma, l) + 1)
        point = ma + another_length
        right_ma = min(r, right_ma)
        left_ma = max(l, left_ma)

print(max(ma2, point))
Problem p02883 (python)

Fixed submission:
import numpy as np
N, K = map(int, input().split())
A = np.array(list(map(int, input().split())))
F = np.array(list(map(int, input().split())))
A = np.sort(A)[::-1]
F = np.sort(F)
# 二部探索法　Aの最大値をどこまで減らせるか
if A.sum() <= K:
    print(0)
    exit()
if K == 0:
    print((A * F).max())
up = (A * F).max() # 可能 mid は完食にかかる時間
low = 0 # 不可能
while up > low + 1:
    mid = (up + low) // 2
    if (A - np.minimum(A, (mid // F))).sum() <= K: #可能
        up = mid
    else:
        low = mid
print(up)

Buggy submission (verdict: Runtime Error):
import numpy as np
N, K = map(int, input().split())
A = np.array(list(map(int, input().split())))
F = np.array(list(map(int, input().split())))
A = np.sort(A)[::-1]
F = np.sort(F)
# 二部探索法　Aの最大値をどこまで減らせるか
if A.sum() <= K:
    print(0)
    exit()
if K == 0:
    print((A * F).max())
up = (A * F).max() # 可能 mid は完食にかかる時間
low = 0 # 不可能
while up > low + 1:
    mid = (up + low) // 2
    if (A - min(A, (mid // F))).sum() <= K: #可能
        up = mid
    else:
        low = mid
print(up)
Problem p02900 (python)

Fixed submission:
import fractions

A, B = map(int, input().split())

GCD = fractions.gcd(A, B)

def pf(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

print(len(set(pf(GCD))) + 1)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10 ** 7)

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n //= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(n)
  return table

A, B = map(int, input().split())
x = gcd(A, B)
prime_list = prime_decomposition(x)
s = set(prime_list)
s.add(1)
for y in s:
    if y == x and len(s) != 1:
        s -= {x}
        
print(len(s))

Buggy submission (verdict: Runtime Error):

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n //= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(n)
  return table

A, B = map(int, input().split())
x = gcd(A, B)
prime_list = prime_decomposition(x)
s = set(prime_list)
s.add(1)
for y in s:
    if y == x and len(s) != 1:
        s -= {x}
        
print(len(s))
Problem p02901 (python)

Fixed submission:
def main():
    N, M = map(int, input().split())
    b_cnt = 2 ** N #箱の数は最大12個
    INF = 10 ** 9
    dp = [INF] * b_cnt
    dp[0] = 0

    for i in range(M):
        a, b = map(int, input().split())
        c = sum([2 ** (int(x)-1) for x in list(input().split())])
        for j in range(b_cnt):
            if dp[j|c] > dp[j] + a:
                dp[j|c] = dp[j] + a

    if dp[-1] == INF:
        print(-1)
    else:
        print(dp[-1])

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
bit_cnt = 2 ** N # 箱は最大で12個
INF = 10 ** 10
dp = [INF] * bit_cnt
dp[0] = 0
for _ in range(M):
    price, b = lr()
    open = sum([2 ** (x-1) for x in lr()]) # 1と3の箱を開ける鍵なら101となる
    for j in range(bit_cnt):
        if dp[j|open] > dp[j] + price:
            dp[j|open] = dp[j] + price

if dp[-1] == INF:
    prnit(-1)
else:
    print(dp[-1])
# 解き直し08

Buggy submission (verdict: Runtime Error):
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# Nが小さいのでdfs
N, M = lr()
keys = [None] * (M+1) # 1-indexed
for i in range(M):
    a, b = lr()
    c = set(lr())
    keys[i+1] = (a, c)

def dfs(m, fee, open):
    global answer
    if m == M+1:
        if len(open) == N:
            answer = min(answer, fee)
    else:
        dfs(m+1, fee+keys[m][0], open.union(keys[m][1]))
        dfs(m+1, fee, open)

INF = 10 ** 10
answer = INF
dfs(1, 0, set())
print(-1 if answer == INF else answer)
# 38

Buggy submission (verdict: Runtime Error):
# 鍵の種類は12だからdfs で行けそう
N, M = map(int, input().split())
A = []
C = []
for i in range(M):
    a, b = map(int, input().split())
    c = set(list(map(int, input().split())))
    A.append(a)
    C.append(c)

def dfs(i, sum, box):
    global answer
    if i == M:
        if len(box) == N:
            answer = min(answer, sum)
    else:
        dfs(i+1, sum, box)
        dfs(i+1, sum+A[i], box|C[i])

INF = 10 ** 7
answer = INF
box = set()
dfs(0, 0, box)
#print(A)
#print(C)
if answer == INF:
    print(-1)
else:
    print(answer)