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

Fixed submission:
import fractions

def read():
    A, B = map(int, input().strip().split())
    return A, B

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

def solve(A, B):
    gcd = fractions.gcd(A, B)
    divisors = sorted(make_divisors(gcd))
    table = [True] * len(divisors)
    for i in range(1, len(divisors)):
        for j in range(i+1, len(divisors)):
            if table[j] and divisors[j] % divisors[i] == 0:
                table[j] = False
    divisors = [divisors[i] for i in range(len(divisors)) if table[i]]
    return len(divisors)

if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))

Buggy submission (verdict: Runtime Error):
import math

def read():
    A, B = map(int, input().strip().split())
    return A, B

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

def solve(A, B):
    gcd = math.gcd(A, B)
    divisors = sorted(make_divisors(gcd))
    table = [True] * len(divisors)
    for i in range(1, len(divisors)):
        for j in range(i+1, len(divisors)):
            if table[j] and divisors[j] % divisors[i] == 0:
                table[j] = False
    divisors = [divisors[i] for i in range(len(divisors)) if table[i]]
    return len(divisors)

if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))
Problem p02973 (python)

Fixed submission:
import sys
input = sys.stdin.readline
from bisect import bisect_left, bisect_right


def read():
    N = int(input().strip())
    A = [int(input().strip()) for _ in range(N)]
    return N, A


def solve(N, A, INF=10**9+1):
    # LIS
    # dp[i]: 長さiの最長増加部分列(A[i]<A[j])のうち、最も小さい数字
    dp = [INF for i in range(N)]
    for i in range(N):
        a = A[N-i-1]
        idx = bisect_right(dp, a)
        dp[idx] = a
    return bisect_right(dp, INF-1)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
import numpy as np
from numba import njit


def read():
    N = int(input().strip())
    A = [int(input().strip()) for _ in range(N)]
    return N, A


@njit
def segtree_init(size, init_value=10**8, dtype=np.int32):
    """初期化"""
    n = 1
    while size > 1:
        size >>= 1
        n += 1
    treesize = n * 2
    st = np.full(treesize, init_value, dtype=dtype)
    st_idx = np.arange(treesize, dtype=dtype)
    offset = st.shape[0] // 2
    return st, st_idx, offset

@njit
def segtree_update(st, st_idx, offset, key, value, init_value=10**8):
    """値の更新"""
    k = offset + key
    st[k] = value
    k >>= 1
    while k > 0:
        if st[k * 2] <= st[k * 2 + 1]:
            st[k] = st[k * 2]
            st_idx[k] = st_idx[k * 2]
        else:
            st[k] = st[k * 2 + 1]
            st_idx[k] = st_idx[k * 2 + 1]
        k >>= 1

    
@njit
def _segtree_find_le(st, st_idx, offset, value, k=1, init_value=10**8):
    """value以下の最大の値を検索し、(index, value)の組を返す
    k: 着目しているノード (1-indexed)
    l: 探索区間 st[l, r) の左端 (0-indexed)
    r: 探索区間 st[l, r) の右端 (0-indexed)
    """
    if value < st[k]:
        return (st.shape[0], -init_value)
    elif value == st[k] or k >= offset:
        return (st_idx[k], st[k])
    else:
        li, lv = _segtree_find_le(st, st_idx, offset, value, k * 2, init_value=init_value)
        ri, rv = _segtree_find_le(st, st_idx, offset, value, k * 2 + 1,  init_value=init_value)
        mi = li if lv >= rv else ri
        mv = lv if lv >= rv else rv
        if mi < st.shape[0]:
            return (mi, mv)
        else:
            return (st.shape[0], -init_value)
    
@njit
def segtree_find_le(st, st_idx, offset, value, init_value=10**8):
    """value以下の最大値を検索し、(index, value)の組を1つ返す
    見つからない場合は-1を返す
    """
    i, v = _segtree_find_le(st, st_idx, offset, value, k=1, init_value=init_value)
    if i == st.shape[0]:
        return (-1, init_value)
    else:
        return (i - offset, v)


def solve(N, A, INF=10**9+1):
    st, st_idx, offset = segtree_init(N)
    l = 0
    for a in A[::-1]:
        k, v = segtree_find_le(st, st_idx, offset, -a-1)  # 以下を未満にするため-1
        if k == -1:
            segtree_update(st, st_idx, offset, l, -a)
            l += 1
        else:
            segtree_update(st, st_idx, offset, k, -a)
    return l


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))
Problem p03046 (python)

Fixed submission:
import sys
input = sys.stdin.readline
from functools import reduce
from operator import xor


def read():
    M, K = map(int, input().strip().split())
    return M, K


def solve(M, K):
    seq = [str(0) for i in range(2**(M+1))]
    if K == 0:
        for i in range(2**M):
            seq[2*i] = str(i)
            seq[2*i+1] = str(i)
    else:
        if K >= 2**M:
            return -1
        # (A) K ... 0 K 0 rev(...), xor(...) == K の形を作れればOK
        S = [a for a in range(2**M) if a not in (0, K)]
        if len(S) == 0 or reduce(xor, S) != K:
            return -1
            
        j = 0
        for i in range(2**M-2):
            j += 1
            if j == K:
                j += 1
            seq[i+1] = str(j)
            seq[2**(M+1) - i - 1] = str(j)
        seq[0] = str(K)
        seq[2**M] = str(K)
        
    return " ".join(seq)


if __name__ == '__main__':
    inputs = read()
    print(solve(*inputs))

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
from functools import reduce
from operator import xor


def read():
    M, K = map(int, input().strip().split())
    return M, K


def solve(M, K):
    seq = [str(0) for i in range(2**(M+1))]
    if K == 0:
        for i in range(2**M):
            seq[2*i] = str(i)
            seq[2*i+1] = str(i)
    else:
        # K ... 0 K rev(...) 0, xor(...) == K の形を作れればOK
        S = [a for a in range(2**M) if a not in (0, K)]
        if M == 1 or reduce(xor, S) != K:
            return -1
        j = 0
        for i in range(2**M-2):
            j += 1
            if j == K:
                j += 1
            seq[i+1] = str(j)
            seq[2**(M+1) - i - 2] = str(j)
        seq[0] = str(K)
        seq[2**M] = str(K)
    return " ".join(seq)
    


if __name__ == '__main__':
    inputs = read()
    print(solve(*inputs))
Problem p03136 (python)

Fixed submission:
def read():
    N = int(input().strip())
    L = map(int, input().strip().split())
    return N, L


def solve(N, L):
    L = sorted(L)
    return "Yes" if L[-1] < sum(L[:-1]) else "No"


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

Buggy submission (verdict: Runtime Error):
def read():
    N = int(input().strip())
    L = map(int, input().strip().split())
    return N, L


def solve(N, L):
    L = sorted(L)
    return "Yes" if L[-1] < sum(L[:-1]) else "No"


if __name__ == '__main__':
    inputs = read()
    print("%f" % solve(*inputs))
Problem p03138 (python)

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


def read():
    N, K = map(int, input().strip().split())
    A = list(map(int, input().strip().split()))
    return N, K, A


def solve(N, K, A):
    L = max(K, max(A), 1).bit_length()
    k = [0 for i in range(L)]
    i = 0
    while K:
        k[i] += K & 1
        i += 1
        K >>= 1
    b = [0 for i in range(L)]
    for a in A:
        i = 0
        x = a
        while x:
            b[i] += x & 1
            i += 1
            x >>= 1
    k = k[::-1]
    b = b[::-1]
    # dp[i][1]: 上位iビットがKと等しいときの最大値
    # dp[i][0]: 上位iビットがKより小さいときの最大値
    dp = [[-1, -1] for i in range(L+1)]
    dp[0][1] = 0
    for i in range(L):
        if dp[i][0] >= 0:
            dp[i+1][0] = (dp[i][0] << 1) + max(b[i], N-b[i])
        if dp[i][1] >= 0:
            if k[i] == 1:
                dp[i+1][0] = max(dp[i+1][0], (dp[i][1] << 1) + b[i])
                dp[i+1][1] = (dp[i][1] << 1) + (N-b[i])
            else:
                dp[i+1][1] = (dp[i][1] << 1) + (b[i])
    return max(dp[L][1], dp[L][0])


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Buggy submission (verdict: Runtime Error):
def read():
    N, K = map(int, input().strip().split())
    A = map(int, input().strip().split())
    return N, K, A


def binary_digits(x):
    digit = 0
    while x > 0:
        x >>= 1
        digit += 1
    return digit


def maximum_X(N, K, A):
    digitK = binary_digits(K)
    counts = []
    bitmask = 1
    for d in range(digitK):
        count = 0
        for i in range(N):
            if A[i] & bitmask == bitmask:
                count += 1
        counts.append(count)
        bitmask <<= 1

    X = 0
    bitmask = 1
    for d in range(digitK):
        if counts[d] * 2 < N:
            X += bitmask
        bitmask <<= 1
    return X


def f(x, A):
    y = 0
    for a in A:
        y += (x ^ a)
    return y


def solve(N, K, A):
    X = maximum_X(N, K, A)
    return f(X, A)


if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))
Problem p03160 (python)

Fixed submission:
def read():
    N = int(input().strip())
    H = list(map(int, input().strip().split()))
    return N, H

def solve(N, H, INF=10**9):
    dp = [INF for i in range(N)]
    dp[0] = 0
    for i in range(1, N):
        left, right = INF, INF
        if i >= 1:
            left = dp[i-1] + abs(H[i-1] - H[i])
        if i >= 2:
            right = dp[i-2] + abs(H[i-2] - H[i])
        dp[i] = min(left, right)
    return dp[N-1]

if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

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


def read():
    N = int(input().strip())
    H = list(map(int, input().strip().split()))
    return N, H

def solve(N, H, INF=10**9):
    dp = [INF for i in range(N)]
    dp[0] = 0
    for i in range(1, N):
        left, right = INF, INF
        if i >= 1:
            left = dp[i-1] + abs(H[i-1] - H[i])
        if i >= 2:
            right = dp[i-2] + abs(H[i-2] - H[i])
        dp[i] = min(left, right)
    return dp[N-1]

if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))
Problem p03193 (python)

Fixed submission:
def read():
    N, H, W = list(map(int, input().strip().split()))
    A = []
    B = []
    for i in range(N):
        a, b = list(map(int, input().strip().split()))
        A.append(a)
        B.append(b)
    return N, H, W, A, B


def solve(N, H, W, A, B):
    count = 0
    for i in range(N):
        if A[i] >= H and B[i] >= W:
            count += 1
    return count


if __name__ == '__main__':
    inputs = read()
    print(solve(*inputs))

Buggy submission (verdict: Runtime Error):
def read():
    N, H, W = list(map(int, input().strip().split()))
    A = []
    B = []
    for i in range(N):
        a, b = list(map(int, input().strip().split()))
        A.append(a)
        B.append(b)
    return N, H, W, A, B


def solve(N, H, W, A, B):
    count = 0
    for i in range(N):
        if A[i] >= H and B[i] >= W:
            count += 1
    return count


if __name__ == '__main__':
    inputs = read()
    print(solve(inputs))
Problem p03200 (python)

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


def read():
    S = list(input().strip())
    return S,

def solve(S):
    N = len(S)
    count = 0
    l = 0
    r = N-1
    while r >= 0 and S[r] != 'W':
        r-=1
    s = list()
    c = 0
    for i in range(r, -1, -1):
        d = r - i
        if S[i] == 'B':
            s.append(d - c)
            c += 1
    return sum(s)

if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline


def read():
    S = list(input().strip())
    return S,

def solve(S):
    N = len(S)
    count = 0
    l = 0
    r = N-1
    while S[r] != 'W':
        r-=1
    s = list()
    c = 0
    for i in range(r, -1, -1):
        d = r - i
        if S[i] == 'B':
            s.append(d - c)
            c += 1
    return sum(s)

if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))
Problem p03361 (python)

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(200000)


def read():
    H, W = map(int, input().strip().split())
    S = []
    for i in range(H):
        s = list(input().strip())
        S.append(s)
    return H, W, S


def solve(H, W, S):
    if H == 1 and  W == 1 and S[0][0] == "#":
        return "No"
    
    dd = [(1, 0), (0, 1), (-1, 0), (0, -1)]

    def dfs(y, x):
        depth = 1
        S[y][x] = "."
        for dy, dx in dd:
            ny = y + dy
            nx = x + dx
            if 0 <= ny < H and 0 <= nx < W and S[ny][nx] == "#":
                depth = max(depth, dfs(ny, nx) + 1)
        return depth

    for i in range(H):
        for j in range(W):
            if S[i][j] == "#":
                depth = dfs(i, j)
                if depth == 1:
                    return "No"
    return "Yes"


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline


def read():
    H, W = map(int, input().strip().split())
    S = []
    for i in range(H):
        s = list(input().strip())
        S.append(s)
    return H, W, S


def solve(H, W, S):
    dd = [(1, 0), (0, 1), (-1, 0), (0, -1)]

    def dfs(y, x):
        depth = 0
        S[y][x] = "."
        for dy, dx in dd:
            ny = y + dy
            nx = x + dx
            if 0 <= ny < H and 0 <= nx < W and S[ny][nx] == "#":
                depth = max(depth, dfs(ny, nx) + 1)
        return depth

    for i in range(H):
        for j in range(W):
            depth = dfs(i, j)
            if depth == 1:
                return "No"
    return "Yes"


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))
Problem p02555 (python)

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

s=int(input())

INF=10**9+7

def modcomb(n,k,m):
    fac=[0]*(n+1)
    finv=[0]*(n+1)
    inv=[0]*(n+1)
    fac[0]=fac[1]=1
    finv[0]=finv[1]=1
    inv[1]=1
    for i in range(2,n+1):
        fac[i]=fac[i-1]*i%m
        inv[i]=m-inv[m%i]*(m//i)%m
        finv[i]=finv[i-1]*inv[i]%m
    return fac[n]*(finv[k]*finv[n-k]%m)%m

ans=0
if s==3:
    ans=1
else:
    for n in range(1,667):
        if s-3*n>=0:
            ans=(ans+modcomb(s-2*n-1,n-1,INF))%INF

print(ans)

Buggy submission (verdict: Runtime Error):
import sys
input=sys.stdin.readline

s=int(input())

INF=10**9+7

def modcomb(n,k,m):
    fac=[0]*(n+1)
    finv=[0]*(n+1)
    inv=[0]*(n+1)
    fac[0]=fac[1]=1
    finv[0]=finv[1]=1
    inv[1]=1
    for i in range(2,n+1):
        fac[i]=fac[i-1]*i%m
        inv[i]=m-inv[m%i]*(m//i)%m
        finv[i]=finv[i-1]*inv[i]%m
    return fac[n]*(finv[k]*finv[n-k]%m)%m

ans=0
for n in range(1,667):
    if s-3*n>=0:
        ans=(ans+modcomb(s-2*n-1,n-1,INF))%INF

print(ans)
Problem p02768 (python)

Fixed submission:
import sys
input=sys.stdin.readline
n,a,b=map(int,input().split())
INF=10**9+7
def modinv(a,m):
    b=m
    (x,lastx)=(0,1)
    (y,lasty)=(1,0)
    while not b==0:
        q=a//b
        (a,b)=(b,a%b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx%m
ans=0
ans=(ans+pow(2,n,INF)-1)%INF
bunsi=1
bunbo=1
for i in range(a):
    bunsi=(bunsi*(n-i))%INF
    bunbo=(bunbo*(i+1))%INF
x=(bunsi*modinv(bunbo,INF))%INF
bunsi=1
bunbo=1
for i in range(b):
    bunsi=(bunsi*(n-i))%INF
    bunbo=(bunbo*(i+1))%INF
y=(bunsi*modinv(bunbo,INF))%INF
ans=(ans-x-y)%INF
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
input=sys.stdin.readline
n,a,b=map(int,input().split())
INF=10**9+7
def modcomb(n,k,m):
    fac=[0]*(n+1)
    finv=[0]*(n+1)
    inv=[0]*(n+1)
    fac[0]=fac[1]=1
    finv[0]=finv[1]=1
    inv[1]=1
    for i in range(2,n+1):
        fac[i]=fac[i-1]*i%m
        inv[i]=m-inv[m%i]*(m//i)%m
        finv[i]=finv[i-1]*inv[i]%m
    return fac[n]*(finv[k]*finv[n-k]%m)%m
ans=0
ans=(ans-modcomb(n,a,INF)-modcomb(n,b,INF))%INF
ans=(ans+pow(2,n,INF)-1)%INF
print(ans)
Problem p02985 (python)

Fixed submission:
INF=10**9+7
n,k=map(int,input().split())
graph=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
ans=1
check=[False]*n
import sys
sys.setrecursionlimit(10**6)
stack=[0]
ans=1
while len(stack)>0:
    x=stack.pop()
    check[x]=True
    count=0
    for i in graph[x]:
        if not check[i]:
            count+=1
            stack.append(i)
    if x==0:
        temp=1
        for i in range(count):
            temp=temp*(k-1-i)%INF
        ans=ans*temp%INF
    else:
        temp=1
        for i in range(count):
            temp=temp*(k-2-i)%INF
        ans=ans*temp%INF
print((ans*k)%INF)

Buggy submission (verdict: Runtime Error):
INF=10**9+7
n,k=map(int,input().split())
graph=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
ans=1
check=[False]*n
def dfs(x):
    global ans
    check[x]=True
    count=0
    for i in graph[x]:
        if not check[i]:
            count+=1
            dfs(i)
    if x==0:
        temp=1
        for i in range(count):
            temp=temp*(k-1-i)%INF
        ans=ans*temp%INF
    else:
        temp=1
        for i in range(count):
            temp=temp*(k-2-i)%INF
        ans=ans*temp%INF
dfs(0)
print((ans*k)%INF)
Problem p03044 (python)

Fixed submission:
import sys
sys.setrecursionlimit(100002)
n=int(input())
point=[]
answer=[]
already=[]
for i in range(n):
    point.append([])
    answer.append(0)
    already.append(0)
for i in range(n-1):
    u,v,w=map(int,input().split())
    point[u-1].append((v-1,w))
    point[v-1].append((u-1,w))
def dfs(now,c):
    answer[now]=c
    already[now]=1
    for i in point[now]:
        if already[i[0]]==1:
            pass
        else:
            if i[1]%2==0:
                dfs(i[0],c)
            else:
                if c==0:
                    dfs(i[0],1)
                else:
                    dfs(i[0],0)
dfs(0,0)
for i in answer:
    print(i)

Buggy submission (verdict: Runtime Error):
n=int(input())
point=[]
answer=[]
already=[]
for i in range(n):
    point.append([])
    answer.append(0)
    already.append(0)
for i in range(n-1):
    u,v,w=map(int,input().split())
    point[u-1].append((v-1,w))
    point[v-1].append((u-1,w))
def dfs(now,c):
    answer[now]=c
    already[now]=1
    for i in point[now]:
        if already[i[0]]==1:
            pass
        else:
            if i[1]%2==0:
                dfs(i[0],c)
            else:
                if c==0:
                    dfs(i[0],1)
                else:
                    dfs(i[0],0)
dfs(0,0)
for i in answer:
    print(i)
Problem p03086 (python)

Fixed submission:
s=input()
s_list=[]
length=0
for i in s:
    if i=='A' or i=='T' or i=='C' or i=='G':
        length=length+1
    else:
        s_list.append(length)
        length=0
s_list.append(length)
print(max(s_list))

Buggy submission (verdict: Runtime Error):
s=input()
s_list=[]
length=0
for i in s:
    if i=='A' or i=='T' or i=='C' or i=='G':
        length=length+1
    else:
        s_list.append(length)
        length=0
print(max(s_list))
Problem p03087 (python)

Fixed submission:
n,q=map(int,input().split())
s=input()
list_ac=[0]
number=0
for i in range(0,n):
    if s[i:i+2]=='AC':
        number=number+1
        list_ac.append(number)
    else:
        list_ac.append(number)
for i in range(0,q):
    l,r=map(int,input().split())
    print(list_ac[r-1]-list_ac[l-1])

Buggy submission (verdict: Runtime Error):
n,q=map(int,input().split())
s=input()
list_ac=[]
number=0
for i in range(0,len(s)):
    if s[i]=='A':
        state=1
        list_ac.append(number)
    elif s[i]=='C':
        if state==1:
            number=number+1   
        list_ac.append(number)
        state=0
    else:
        state=0
        list_ac.append(number)
list_ac.append(list_ac[-1])
for i in range(0,q):
    l,r=map(int,input().split())
    print(list_ac[r-1]-list_ac[l-1])

Buggy submission (verdict: Runtime Error):
n,q=map(int,input().split())
s=input()
list_ac=[]
number=0
for i in range(0,n):
    if s[i]=='A':
        state=1
        list_ac.append(number)
    elif s[i]=='C':
        if state==1:
            number=number+1   
        list_ac.append(number)
        state=0
    else:
        state=0
        list_ac.append(number)
print(list_ac)
for i in range(0,q):
    l,r=map(int,input().split())
    print(list_ac[r-1]-list_ac[l-1])

Buggy submission (verdict: Runtime Error):
n,q=map(int,input().split())
s=input()
list_ac=[]
number=0
for i in range(0,len(s)):
    if s[i]=='A':
        state=1
        list_ac.append(number)
    elif s[i]=='C':
        if state==1:
            number=number+1   
        list_ac.append(number)
        state=0
    else:
        state=0
        list_ac.append(number)
for i in range(0,q):
    l,r=map(int,input().split())
    print(list_ac[r-1]-list_ac[l-1])

Buggy submission (verdict: Runtime Error):
n,q=map(int,input().split())
s=input()
list_ac=[]
for i in range(0,len(s)):
    if s[i]=='A':
        place=i
        state=1
    elif s[i]=='C':
        if state==1:
            list_ac.append(place)
        state=0
    else:
        state=0      
for i in range(0,q):
    l,r=map(int,input().split())
    count=0
    for j in list_ac:
        if l-1<=j<=r-2:
            count=count+1
        elif j>r-2:
            break
    print(count)
Problem p03103 (python)

Fixed submission:
n,m=map(int,input().split())
list_ab=[]
for i in range(0,n):
    a,b=map(int,input().split())
    list_ab.append((a,b))
list_ab=sorted(list_ab)
cost=0
for i in range(0,n):
    a=list_ab[i][0]
    b=list_ab[i][1]
    if m<=b:
        cost=cost+a*m
        break
    else:
        cost=cost+a*b
        m=m-b
print(cost)

Buggy submission (verdict: Runtime Error):
n,m=map(int,input().split())
dict_ab={}
for i in range(0,n):
    a,b=map(int,input().split())
    dict_ab[a]=b
list_ab=sorted(dict_ab.items())
cost=0
for i in range(0,n):
    a=list_ab[i][0]
    b=list_ab[i][1]
    if m<=b:
        cost=cost+a*m
        break
    else:
        cost=cost+a*b
        m=m-b
print(cost)
Problem p03148 (python)

Fixed submission:
n,k=map(int,input().split())
sushi=[]
for i in range(n):
    sushi.append([])
for i in range(n):
    t,d=map(int,input().split())
    sushi[t-1].append(d)
Max=[]
Rest=[]
v=0
for i in sushi:
    if not i==[]:
        Max.append(max(i))
        i.remove(max(i))
        for j in i:
            Rest.append(j)
        v=v+1
Max.sort(reverse=True)
Rest.sort(reverse=True)
Max_s=[]
Rest_s=[0]
Sum=0
for i in Max:
    Sum=Sum+i
    Max_s.append(Sum)
Sum=0
l_r=0
for i in Rest:
    Sum=Sum+i
    Rest_s.append(Sum)
    l_r=l_r+1
ans=0
for i in range(1,min(k,v)+1):
    if k-i<=l_r:
        temp=Max_s[i-1]+Rest_s[k-i]+i**2
        if ans<temp:
            ans=temp
print(ans)

Buggy submission (verdict: Runtime Error):
n,K=map(int,input().split())
s_list=[]
for i in range(n):
    s_list.append([])
for i in range(n):
    t,d=map(int,input().split())
    s_list[t-1].append(d)
s_list=[i for i in s_list if not i==[]]
n_list=[]
for i in s_list:
    i.sort(reverse=True)
    n_list.append(len(i))
dp={}
def f(i,v,k):
    if (i,v,k) in dp:
        return dp[(i,v,k)]
    else:
        if i==len(n_list):
            if k==0:
                return 0
            else:
                return -10**9
        elif k==0:
            return 0
        else:
            Max=f(i+1,v,k)
            for j in range(0,n_list[i]):
                if k-j-1>=0:
                    m=f(i+1,v+1,k-j-1)+2*v+1+sum(s_list[i][0:j+1])
                    if m>Max:
                        Max=m
            dp[(i,v,k)]=Max
            return(Max)
print(f(0,0,K))