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

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

list0 = []
list1 = []
set1 = set()

td = []
for i in range(N):
    t, d = map(int, input().split())
    td.append((t, d))

td.sort(key=lambda x: (x[0], -x[1]))

for t, d in td:
    if t in set1:
        list0.append(d)
    else:
        set1.add(t)
        list1.append(d)

list0.sort(reverse=True)
list1.sort(reverse=True)

various = min(K, len(list1))
selected0 = []
selected1 = []
for i in range(various):
    selected1.append(list1.pop(0))
if K > various:
    for i in range(K - various):
        selected0.append(list0.pop(0))


ans = sum(selected0) + sum(selected1) + various ** 2

mn = selected1[-1]
sum0 = sum(selected0)
sum1 = sum(selected1)
while list0 and list0[0] > mn:
    sum0 += list0.pop(0)
    sum1 -= selected1.pop(-1)
    various -= 1
    tmp = sum0 + sum1 + various ** 2
    if tmp <= ans:
        break
    ans = tmp

print(ans)

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

list0 = []
list1 = []
set1 = set()
for i in range(N):
    t, d = map(int, input().split())
    if t in set1:
        list0.append(d)
    else:
        set1.add(t)
        list1.append(d)

list0.sort(reverse=True)
list1.sort(reverse=True)

various = max(K, len(list1))
selected = []
for i in range(various):
    selected.append(list1.pop(0))

ans = sum(selected) + various ** 2

while list0 and list0[0] > selected[-1]:
    selected.pop(-1)
    selected.insert(0, list0.pop(0))
    various -= 1
    tmp = sum(selected) + various ** 2
    if tmp <= ans:
        break
    ans = tmp

print(ans)

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

list0 = []
list1 = []
set1 = set()
for i in range(N):
    t, d = map(int, input().split())
    if t in set1:
        list0.append(d)
    else:
        set1.add(t)
        list1.append(d)

list0.sort(reverse=True)
list1.sort(reverse=True)

various = max(K, len(list1))
selected = []
for i in range(various):
    selected.append(list1.pop(0))

ans = sum(selected) + various ** 2

while list0 and list0[0] > selected[-1]:
    selected.pop(-1)
    selected.insert(0, list0.pop(0))
    various -= 1
    tmp = sum(selected) + various ** 2
    if tmp <= ans:
        break
    ans = tmp

print(ans)
Problem p03149 (python)

Fixed submission:
l = sorted(input().split())
if ''.join(l) == '1479':
    print('YES')
else:
    print('NO')

Buggy submission (verdict: Runtime Error):
l = sorted(map(int, input().split()))
if ''.join(l) == '1479':
    print('YES')
else:
    print('NO')
Problem p03163 (python)

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

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
weight = [0]
value = [0]
for i in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)

for i in range(N):
    i += 1
    for sum_w in range(W+1):
        # i 番目の品物を選ぶ場合
        if sum_w >= weight[i]:
            dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w - weight[i]] + value[i])
        # i 番目の品物を選ばない場合
        dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w])

print(dp[N][W])

Buggy submission (verdict: Runtime Error):

N, W = map(int, input().split())
weight = []
value = []
for i in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)
dp = [[0 for _ in range(W)] for _ in range(N)]
for i in range(N):
    for j in range(W+1):
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        if j - weight[i] >= 0:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j-weight[i]]+value[i])
print(dp[N][W])
Problem p03164 (python)

Fixed submission:
N, W = map(int, input().split())
INF = float('inf')
MAX_V = 100100

dp = [[INF for _ in range(MAX_V+1)] for _ in range(N+1)]
dp[0][0] = 0
weight = []
value = []
for i in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)

for i in range(N):
    for sum_v in range(MAX_V + 1):
        # i 番目の品物を選ぶ場合
        if sum_v - value[i] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - value[i]] + weight[i])
        # i 番目の品物を選ばない場合
        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])

ans = 0
for sum_v in range(MAX_V + 1):
    if dp[N][sum_v] <= W:
        ans = sum_v

print(ans)

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

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
weight = []
value = []
for i in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)

for i in range(N):
    for sum_w in range(W+1):
        # i 番目の品物を選ぶ場合
        if sum_w >= weight[i]:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - weight[i]] + value[i])
        # i 番目の品物を選ばない場合
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])

print(dp[N][W])
Problem p03166 (python)

Fixed submission:
import heapq
from collections import defaultdict, deque
from math import ceil, factorial
import sys
sys.setrecursionlimit(10**7)

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lmii = lambda: list(map(int, input().split()))
smii = lambda: sorted(map(int, input().split()))
# ---
N, M = mii()
edge = defaultdict(list)
memo = defaultdict(int)
done = defaultdict(bool)


def dp(v):
    if done[v]:
        return memo[v]
    ret = 0
    for to in edge[v]:
        ret = max(ret, dp(to) + 1)
    done[v] = True
    memo[v] = ret
    return ret


for i in range(M):
    x, y = mii()
    edge[x].append(y)
ans = 0
for v in range(1, N+1):
    ans = max(ans, dp(v))

print(ans)

Buggy submission (verdict: Runtime Error):
import heapq
from collections import defaultdict, deque
from math import ceil, factorial

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lmii = lambda: list(map(int, input().split()))
smii = lambda: sorted(map(int, input().split()))

N, M = mii()
edge = defaultdict(list)
memo = defaultdict(int)
done = defaultdict(bool)


def dp(v):
    if done[v]:
        return memo[v]
    ret = 0
    for to in edge[v]:
        ret = max(ret, dp(to) + 1)
    done[v] = True
    memo[v] = ret
    return ret


for i in range(M):
    x, y = mii()
    edge[x].append(y)
ans = 0
for v in range(1, N+1):
    ans = max(ans, dp(v))

print(ans)
Problem p03282 (python)

Fixed submission:
import re

S = input().rstrip()
K = int(input())

reg = re.search(r'[2-9]', S)
if reg:
    i = reg.start()
else:
    i = len(S) + 1


if K < i + 1:
    print(1)
else:
    if S[0] == '1':
        print(S[i])
    else:
        print(S[0])

Buggy submission (verdict: Runtime Error):
import re

S = input().rstrip()
K = int(input())

i = re.search(r'[2-9]', S).start()

if K < i + 1:
    print(1)
else:
    if S[0] == '1':
        print(S[i])
    else:
        print(S[0])
Problem p03330 (python)

Fixed submission:
from copy import deepcopy
# 多次元配列を作成する
def make_multi_list(initial, degree):
    ans = [initial for _ in range(degree[-1])]
    for d in reversed(degree[:-1]):
        ans = [deepcopy(ans) for _ in range(d)]
    return ans


N, C = map(int, input().split())
INF = float("inf")
D = []
for i in range(C):
    D.append(list(map(int, input().split())))
c = []
for i in range(N):
    c.append([n - 1 for n in list(map(int, input().split()))])

# 前計算
cost = make_multi_list(0, [3, C])
for i in range(N):
    for j in range(N):
        for k in range(C):
            cost[(i + j) % 3][k] += D[c[i][j]][k]

ans = INF
for i in range(C):
    for j in range(C):
        if i == j:
            continue
        for k in range(C):
            if k in (i, j):
                continue
            ans = min(ans, cost[0][i] + cost[1][j] + cost[2][k])

print(ans)

Buggy submission (verdict: Runtime Error):
N, C = map(int, input().split())
INF = float("inf")
D = []
for i in range(C):
    D.append(list(map(int, input().split())))
c = []
for i in range(N):
    c.append([n - 1 for n in list(map(int, input().split()))])

# 前計算
cost = [[0 for _ in range(3)] for _ in range(C)]
for i in range(N):
    for j in range(N):
        for k in range(C):
            cost[(i + j) % 3][k] += D[c[i][j]][k]

ans = INF
for i in range(C):
    for j in range(C):
        if i == j:
            continue
        for k in range(C):
            if k in (i, j):
                continue
            ans = min(ans, cost[0][i] + cost[1][j] + cost[2][k])

print(ans)
Problem p03355 (python)

Fixed submission:

S = input().strip()
K = int(input())
L = len(S)
substr = set()

for i in range(L):
    for j in range(5):
        s = S[i:min(i+j+1, L)]
        if s:
            substr.add(s)

print(sorted(substr)[K-1])

Buggy submission (verdict: Runtime Error):

import sys

sys.setrecursionlimit(10 ** 7)
# ----------

INF = float("inf")
MOD = 10 ** 9 + 7
# ----------

s = list(input().strip())
K = int(input())
N = len(s)

if N == 1:
    print(s[0])
    exit()
sub = set()
for i in range(N):
    for j in range(N):
        sub.add(s[i:j+1])

print(sorted(sub)[K])

Buggy submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(10 ** 7)
# ----------

INF = float("inf")
MOD = 10 ** 9 + 7
# ----------

s = input().strip()
K = int(input())
N = len(s)

sub = set()
for i in range(N):
    for j in range(N):
        sub.add(s[i:j + 1])

print(sorted(sub)[K])
Problem p03386 (python)

Fixed submission:
def abc():
    a, b, c = map(int, input().split())
    n = range(a, b + 1)
    for s in sorted(set(n[:c]) | set(n[-c:])):
        print(s)


abc()

Buggy submission (verdict: Runtime Error):
def abc():
    a, b, c = map(int, input().split())
    n = list(range(a, b + 1))
    for s in sorted(set(n[:c]) | set(n[-c:])):
        print(s)


abc()

Buggy submission (verdict: Runtime Error):
def abc():
    a, b, c = map(int, input().rstrip().split())
    n = list(range(a, b + 1))
    s = sorted(set(n[:c]) | set(n[-c:]))
    for _s in s:
        print(_s)


abc()

Buggy submission (verdict: Runtime Error):
def abc():
    a, b, c = map(int, input().split())
    n = list(range(a, b + 1))
    s = sorted(set(n[:c]) | set(n[-c:]))
    for _s in s:
        print(_s)


abc()

Buggy submission (verdict: Runtime Error):
def abc():
    a, b, c = map(int, input().split())
    n = list(range(a, b + 1))
    s = sorted(set(n[:c]) | set(n[-c:]))
    for _s in s:
        print(_s)


abc()
Problem p03493 (python)

Fixed submission:
print(sum(map(int, input())))

Buggy submission (verdict: Runtime Error):
print(sum[map(int, input())])
Problem p03504 (python)

Fixed submission:
from collections import defaultdict
from itertools import accumulate


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

timetables = defaultdict(list)
for i in range(N):
    s, t, c = map(int, input().split())
    timetables[c].append([s, t])

for name, times in timetables.items():
    times.sort()
    new = []
    for i, time in enumerate(times):
        s, t = time
        if i == 0:
            new.append([s, t])
            continue
        if s == new[-1][1]:
            new[-1][1] = t
        else:
            new.append([s, t])
    timetables[name] = new

time_count = [0] * 100010
for name, times in timetables.items():
    for s, t in times:
        time_count[s] += 1
        time_count[t + 1] -= 1

acc = accumulate(time_count)

print(max(acc))

Buggy submission (verdict: Runtime Error):

import heapq
from collections import defaultdict, deque
from math import ceil, factorial, gcd
from itertools import accumulate
import sys
import bisect


sys.setrecursionlimit(10 ** 7)
INF = float("inf")
MOD = 10 ** 9 + 7

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lmii = lambda: list(map(int, input().split()))
smii = lambda: sorted(map(int, input().split()))

# ----------

N, K = mii()

channels = defaultdict(list)
for i in range(N):
    s, t, c = mii()
    channels[c].append([s, t])

for name, times in channels.items():
    times.sort()
    new = []
    for i, time in enumerate(times):
        s, t = time
        if i == 0:
            new.append([s, t])
            continue
        if s == new[-1][1]:
            new[-1][1] = t
        else:
            new.append([s, t])
    channels[name] = new

timetable = [0] * 100010
for name, times in channels.items():
    for s, t in times:
        timetable[s] += 1
        timetable[t+1] -= 1

acc = accumulate(timetable)

print(max(acc))

Buggy submission (verdict: Runtime Error):
import heapq
from collections import defaultdict, deque
from math import ceil, factorial, gcd
from itertools import accumulate
import sys
import bisect


sys.setrecursionlimit(10 ** 7)
INF = float("inf")
MOD = 10 ** 9 + 7

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lmii = lambda: list(map(int, input().split()))
smii = lambda: sorted(map(int, input().split()))

# ----------

N, K = mii()

channels = defaultdict(list)
for i in range(N):
    s, t, c = mii()
    channels[c].append([s, t])

for name, times in channels.items():
    times.sort()
    new = []
    for i, time in enumerate(times):
        s, t = time
        if i == 0:
            new.append([s, t])
            continue
        if s == new[-1][1]:
            new[-1][1] = t
        else:
            new.append([s, t])
    channels[name] = new

timetable = [0] * 100010
for name, times in channels.items():
    for s, t in times:
        timetable[s] += 1
        timetable[t+1] -= 1

acc = accumulate(timetable)

print(max(acc))
Problem p03505 (python)

Fixed submission:
ceil = lambda a, b: -(-a // b)

K, A, B = map(int, input().split())
if A >= K:
    print(1)
    exit()
p = A - B
if p <= 0:
    print(-1)
    exit()

ans = 1
ans += ceil(K - A, A - B) * 2
print(ans)

Buggy submission (verdict: Runtime Error):
ceil = lambda a, b: -(-a // b)

K, A, B = map(int, input().split())
if A >= K:
    print(1)
    exit()
p = A - B
if p < 0:
    print(-1)
    exit()

ans = 1
ans += ceil(K - A, A - B) * 2
print(ans)

Buggy submission (verdict: Runtime Error):
ceil = lambda a, b: -(-a // b)

K, A, B = map(int, input().split())
if A >= K:
    print(1)
    exit()
p = A - B
if p < 0:
    print(-1)
    exit()

ans = 1
ans += ceil(K - A, A - B) * 2
print(ans)
Problem p03523 (python)

Fixed submission:
S = input().strip()

if S.find('AA') != -1:
    print('NO')
    exit()

if S.find('KAI') != -1:
    print('NO')
    exit()

if S.find('IAH') != -1:
    print('NO')
    exit()

if S.replace('A', '') == 'KIHBR':
    print('YES')
else:
    print('NO')

Buggy submission (verdict: Runtime Error):
S = input().strip()

K = S.find('K')
I = S.find('I')
H = S.find('H')
B = S.find('B')
R = S.find('R')

if S.find('AA'):
    print('NO')
    exit()

if K in [0, 1] and I >= 0 and H >= 0 and B >= 0 and R >= 0 and \
   I-K in [0, 1] and H-I in [0, 1] and B-H in [0, 1] and R-B in [0, 1] and:
    print('YES')
else:
    print('NO')
Problem p03576 (python)

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

X, Y = [], []
for i in range(N):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)

ans = float('INF')

for left in range(N):
    for right in range(N):
        for top in range(N):
            for bottom in range(N):
                if X[right]-X[left] <= 0:
                    continue
                if Y[top]-Y[bottom] <= 0:
                    continue
                cnt = 0
                for i in range(N):
                    if X[left] <= X[i] <= X[right] and Y[bottom] <= Y[i] <= Y[top]:
                        cnt += 1
                if cnt >= K:
                    ans = min(ans, (X[right]-X[left])*(Y[top]-Y[bottom]))

print(ans)

Buggy submission (verdict: Runtime Error):
import heapq
from collections import defaultdict, deque
from math import ceil, factorial, gcd
from itertools import accumulate
import sys
import bisect

sys.setrecursionlimit(10 ** 7)
INF = float("inf")
MOD = 10 ** 9 + 7

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lmii = lambda: list(map(int, input().split()))
lmsi = lambda: list(map(str, input().split()))
smii = lambda: sorted(map(int, input().split()))

# ----------

N, K = mii()

X, Y = [], []
for i in range(N):
    x, y = mii()
    X.append(x)
    Y.append(y)

ans = INF

for left in range(N):
    for right in range(N):
        for top in range(N):
            for bottom in range(N):
                if X[right]-X[left] <= 0:
                    continue
                if Y[top]-Y[bottom] <= 0:
                    continue
                cnt = 0
                for i in range(N):
                    if X[left] <= X[i] <= X[right] and Y[bottom] <= Y[i] <= Y[top]:
                        cnt += 1
                if cnt >= K:
                    ans = min(ans, (X[right]-X[left])*(Y[top]-Y[bottom]))

print(ans)
Problem p04013 (python)

Fixed submission:
# 配るDP
N, A = map(int, input().split())
X = list(map(int, input().split()))

dp = [[[0 for _ in range(3010)] for __ in range(N+1)] for ___ in range(N+1)]

dp[0][0][0] = 1

for i in range(N):
    for j in range(N):
        for k in range(2500+1):
            if dp[i][j][k]:
                dp[i+1][j][k] += dp[i][j][k]
                dp[i+1][j+1][k+X[i]] += dp[i][j][k]

ans = 0
for n in range(1, N+1):
    ans += dp[N][n][n*A]

print(ans)

Buggy submission (verdict: Runtime Error):
# 配るDP
N, A = map(int, input().split())
X = list(map(int, input().split()))

dp = [[[0 for _ in range(2500+１０)] for __ in range(N+1)] for ___ in range(N+1)]

dp[0][0][0] = 1

for i in range(N):
    for j in range(N):
        for k in range(2500+1):
            dp[i+1][j][k] += dp[i][j][k]
            dp[i+1][j+1][k+X[i]] += dp[i][j][k]

ans = 0
for n in range(1, N+1):
    ans += dp[N][n][n*A]

print(ans)

Buggy submission (verdict: Runtime Error):
# 配るDP
N, A = map(int, input().split())
X = list(map(int, input().split()))

dp = [[[0 for _ in range(３０１０)] for __ in range(N+1)] for ___ in range(N+1)]

dp[0][0][0] = 1

for i in range(N):
    for j in range(N):
        for k in range(2500+1):
            dp[i+1][j][k] += dp[i][j][k]
            dp[i+1][j+1][k+X[i]] += dp[i][j][k]

ans = 0
for n in range(1, N+1):
    ans += dp[N][n][n*A]

print(ans)

Buggy submission (verdict: Runtime Error):
# 配るDP
N, A = map(int, input().split())
X = list(map(int, input().split()))

dp = [[[0 for _ in range(2500+10)] for __ in range(N+1)] for ___ in range(N+1)]

dp[0][0][0] = 1

for i in range(N):
    for j in range(N):
        for k in range(2500+1):
            dp[i+1][j][k] += dp[i][j][k]
            dp[i+1][j+1][k+X[i]] += dp[i][j][k]

ans = 0
for n in range(1, N+1):
    ans += dp[N][n][n*A]

print(ans)
Problem p02647 (python)

Fixed submission:
import copy
from functools import lru_cache
import numpy as np
from numba import njit

#@njit
# @njit('(i8[::1],)', cache=True)
# def func(A):
#     N = len(A)
#     B = np.zeros_like(A)
#     for i in range(N):
#         l = max(0, i - A[i])
#         r = min(i + A[i], N-1)
#         B[l] += 1
#         if r+1 < N:
#             B[r+1] -= 1

#     B = np.cumsum(B)
#     return B

def resolve():
    N, K = map(int, input().split())
    A = np.array(list(map(int, input().split())))

    # N = 2 * 10**5
    # K = 2 * 10**5
    # A = np.array([0] *  N)

    @njit
    def func(A):
        #N = len(A)
        B = np.zeros_like(A)
        for i in range(N):
            l = max(0, i - A[i])
            r = min(i + A[i], N-1)
            B[l] += 1
            if r+1 < N:
                B[r+1] -= 1

        B = np.cumsum(B)
        return B

    for k in range(K):
        #print(k)
        A = func(A)
        if k >= 50:
            break

    print(" ".join(map(str, A)))

if __name__ == "__main__":
    resolve()

Buggy submission (verdict: Runtime Error):
import copy
def resolve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    if K + min(A) >= N:
        print(" ".join(map(str, [N]*N))
        return

    for i in range(K):
        A_next = [0] * len(A)
        for i, a in enumerate(A):
            A_next[i] += 1
            for d in range(1, a+1):
                idx = i - d
                if idx >= 0 and idx < len(A_next):
                    A_next[idx] += 1

                idx = i + d
                if idx >= 0 and idx < len(A_next):
                    A_next[idx] += 1
        A = copy.deepcopy(A_next)

        if min(A) == N:
            break 

    print(" ".join(map(str, A_next)))

if __name__ == "__main__":
    resolve()
Problem p02787 (python)

Fixed submission:
import math

def resolve():
    import sys
    input = sys.stdin.readline
    
    H, N = map(int, input().split())
    v = []
    w = []
    for i in range(N):
        a, b = map(int, input().split())
        v.append(a)
        w.append(b)

    dp = [[0]*H for _ in range(N)]

    # initiate
    for i in range(H):
        dp[0][i] = w[0] * (math.ceil((i + 1) / v[0])) # 魔法1だけでHまで削るのに必要なコスト(MP)

    for i in range(1, N):
        for j in range(H):
            if j+1 < v[i]: 
                # 敵のHPが魔法iで与えるダメージより小さい場合、そのままの組み合わせか新しい魔法1回とで、コストの少ない方を選ぶ
                dp[i][j] = min(dp[i-1][j], w[i])
            else:
                # 大きい場合、そのままの組み合わせと、魔法iを取り込んだ組み合わせで、コストの少ない方を選ぶ
                dp[i][j] = min(dp[i-1][j], dp[i][j - v[i]] + w[i])

    print(dp[N-1][H-1])


if __name__ == "__main__":
    resolve()

Buggy submission (verdict: Runtime Error):
import numpy as np
def resolve():
    import sys
    input = sys.stdin.readline
    
    H, N = map(int, input().split())
    v = []
    w = []
    for i in range(N):
        a, b = map(int, input().split())
        v.append(a)
        w.append(b)

    min_v_idx = np.array(v).argmin()
    W = (H // v[min_v_idx] + 1) * w[min_v_idx]
    dp = [[0]*W for _ in range(N+1)]

    for i in range(N):
        for j in range(W):
            if j < w[i]:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = max(dp[i][j], dp[i + 1][j - w[i]] + v[i])

    INF = 10e10
    res = np.array(dp)
    res = np.where(res < H, INF, res)
    mins = np.where(res == res.min())
    print(min(mins[1]))



if __name__ == "__main__":
    resolve()