Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = [int(input()) for i in range(n)]

color = [a[0]]
for i in range(1,n):
    color.sort(reverse=True)
    for j in range(len(color)):
        if color[j] < a[i]:
            color[j] = a[i]
            break
    else:
        color.append(a[i])

print(len(color))

Fixed submission:
from bisect import *
n = int(input())
a = [int(input()) for i in range(n)]

color = [-a[0]]
for i in range(1,n):
    if -a[i] >= color[-1]:
        color.append(-a[i])
    else:
        idx = bisect_right(color,-a[i])
        color[idx] = -a[i]

print(len(color))

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = [int(input()) for i in range(n)]
color_painted = [1]
color_used = 1
a_mins = {1 : a[-1], }
for i in range(n-2,-1,-1):
    if a_mins[color_used] <= a[i]:
        color_used = 0
        while color_used < len(color_painted):
            color_used += 1
            if a[i] < a_mins[color_used]:
                a_mins[color_used] = a[i]
                break
        else:
            color_used += 1
            a_mins[color_used] = a[i]
            color_painted.append(color_used)
    elif a[i] < a_mins[color_used]:
        a_mins[color_used] = a[i]

print(len(color_painted))

Fixed submission:
from bisect import *
n = int(input())
a = [int(input()) for i in range(n)]

color = [-a[0]]
for i in range(1,n):
    if -a[i] >= color[-1]:
        color.append(-a[i])
    else:
        idx = bisect_right(color,-a[i])
        color[idx] = -a[i]

print(len(color))
Buggy python submission (verdict: Runtime Error):
n, x = (int(i) for i in input().split())
l = [int(i) for i in input().split()]

d = 0
ans = 0
i = 0
while d <= x and i < n+1:
    ans += 1
    d = d + l[i]
    i += 1

print(ans)

Fixed submission:
n, x = (int(i) for i in input().split())
l = [0] + [int(i) for i in input().split()]

d = 0
ans = 0
i = 1
while d <= x:
    ans += 1
    if ans == n+1:
        break
    d = d + l[i]
    i += 1

print(ans)

Buggy python submission (verdict: Runtime Error):
n, x = (int(i) for i in input().split())
l = [int(i) for i in input().split()]

d = 0
ans = 0
i = 0
while d <= x:
    ans += 1
    d = d + l[i]
    i += 1

print(ans)

Fixed submission:
n, x = (int(i) for i in input().split())
l = [0] + [int(i) for i in input().split()]

d = 0
ans = 0
i = 1
while d <= x:
    ans += 1
    if ans == n+1:
        break
    d = d + l[i]
    i += 1

print(ans)
Buggy python submission (verdict: Runtime Error):
// #define _GLIBCXX_DEBUG
// #pragma GCC optimize("Ofast")
#pragma GCC diagnostic ignored "-Wsign-compare"
#include <bits/stdc++.h>
using namespace std;
using i64 = int_fast64_t;
#define rep(i, n) for (i64 i = 0; i < (i64)(n); ++i)
#define reps(i, s, n) for (i64 i = s; i < (i64)(n); ++i)

void solve() {
    int n, k;
    cin >> n >> k;
    int ans = (k != 1 ? n - k : 0);
    cout << ans << "\n";
}
int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    // cout << fixed << setprecision(15);
    solve();
}

Fixed submission:
n, k = (int(i) for i in input().split())
print(n-k if k != 1 else 0)
Buggy python submission (verdict: Runtime Error):
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    XY = [[int(i) for i in input().split()] for j in range(N)]
    XY.sort()
    from collections import Counter
    c = Counter()
    for i in range(N-1):
        for j in range(i+1, N):
            p = XY[j][0] - XY[i][0]
            q = XY[j][1] - XY[i][1]
            c[(p, q)] += 1
    ans = N - c.most_common()[0][1]
    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    N = int(input())
    A = [[int(i) for i in input().split()] for j in range(N)]
    if N == 1:
        return print(1)
    A.sort()
    from collections import defaultdict
    cnt = defaultdict(int)
    for i in range(N):
        for j in range(i+1, N):
            # print(A[i], A[j], (A[j][0] - A[i][0], A[j][1] - A[i][1]))
            cnt[(A[j][0] - A[i][0], A[j][1] - A[i][1])] += 1
    # print(cnt.values())
    ans = (N-1) - (sorted(cnt.values())[-1] - 1)
    print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
def main():
    N = int(input())
    A = [[int(i) for i in input().split()] for j in range(N)]
    A.sort()
    from collections import defaultdict
    cnt = defaultdict(int)
    for i in range(N):
        for j in range(i+1, N):
            # print(A[i], A[j], (A[j][0] - A[i][0], A[j][1] - A[i][1]))
            cnt[(A[j][0] - A[i][0], A[j][1] - A[i][1])] += 1
    # print(cnt.values())
    ans = (N-1) - (sorted(cnt.values())[-1] - 1)
    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    N = int(input())
    A = [[int(i) for i in input().split()] for j in range(N)]
    if N == 1:
        return print(1)
    A.sort()
    from collections import defaultdict
    cnt = defaultdict(int)
    for i in range(N):
        for j in range(i+1, N):
            # print(A[i], A[j], (A[j][0] - A[i][0], A[j][1] - A[i][1]))
            cnt[(A[j][0] - A[i][0], A[j][1] - A[i][1])] += 1
    # print(cnt.values())
    ans = (N-1) - (sorted(cnt.values())[-1] - 1)
    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
n, m = (int(i) for i in input().split())
a = [int(input()) for i in range(m)]
MOD = 10**9 + 7

d = [0] * (n+5)
d[1] = (1 if len(a) == 0 or a[0] != 1 else 0)
d[2] = (d[1] + 1 if len(a) == 0 or 2 not in a else 0)

for i in range(2,n):
    d[i+1] = d[i] + d[i-1]
    if i+1 in a:
        d[i+1] = 0
print(d[n]%MOD)

Fixed submission:
n, m = (int(i) for i in input().split())
a = {int(input()) for i in range(m)}
MOD = 10**9 + 7

d = [0] * (n+5)
d[1] = (0 if 1 in a else 1)
d[2] = (0 if 2 in a else d[1] + 1)

for i in range(2,n):
    d[i+1] = (d[i] + d[i-1])%MOD
    if i+1 in a:
        d[i+1] = 0
print(d[n]%MOD)

Buggy python submission (verdict: Runtime Error):
n, m = (int(i) for i in input().split())
a = [int(input()) for i in range(m)]
MOD = 10**9 + 7

d = [0] * (n+1)
d[1] = (1 if len(a) == 0 or a[0] != 1 else 0)
d[2] = (d[1] + 1 if len(a) == 0 or 2 not in a else 0)

for i in range(2,n):
    d[i+1] = (d[i] + d[i-1])%MOD
    if i+1 in a:
        d[i+1] = 0
print(d[n]%MOD)

Fixed submission:
n, m = (int(i) for i in input().split())
a = {int(input()) for i in range(m)}
MOD = 10**9 + 7

d = [0] * (n+5)
d[1] = (0 if 1 in a else 1)
d[2] = (0 if 2 in a else d[1] + 1)

for i in range(2,n):
    d[i+1] = (d[i] + d[i-1])%MOD
    if i+1 in a:
        d[i+1] = 0
print(d[n]%MOD)

Buggy python submission (verdict: Runtime Error):
n, m = (int(i) for i in input().split())
a = [int(input()) for i in range(m)]
MOD = 10**9 + 7

d = [0] * (n+1)
d[1] = (1 if len(a) == 0 or a[0] != 1 else 0)
d[2] = (d[1] + 1 if len(a) == 0 or 2 not in a else 0)

for i in range(2,n):
    d[i+1] = (d[i] + d[i-1])%MOD
    if i+1 in a:
        d[i+1] = 0
print(d[n]%MOD)

Fixed submission:
n, m = (int(i) for i in input().split())
a = {int(input()) for i in range(m)}
MOD = 10**9 + 7

d = [0] * (n+5)
d[1] = (0 if 1 in a else 1)
d[2] = (0 if 2 in a else d[1] + 1)

for i in range(2,n):
    d[i+1] = (d[i] + d[i-1])%MOD
    if i+1 in a:
        d[i+1] = 0
print(d[n]%MOD)
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10**9 + 7


def main():
    L = input()
    N = len(L)
    dp = [[0]*2 for i in range(N+1)]
    dp[0][0] = 1

    for i in range(N):
        # smaller: 1 -> 1
        if L[i] == "1":
            dp[i+1][1] += dp[i][1] * 3
        else:
            dp[i+1][1] += dp[i][1] * 3
        # smaller: 0 -> 1
        if L[i] == "1":
            dp[i+1][1] += dp[i][0] * 1
        # smaller: 0 -> 0
        if L[i] == "1":
            dp[i+1][0] += dp[i][0] * 2
        else:
            dp[i+1][0] += dp[i][0] * 1
    print((dp[N][0]+dp[N][1]) % MOD)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    # 写経AC
    MOD = 10**9 + 7
    S = input()
    N = len(S)
    dp = [[0]*2 for i in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        # a+b = 0
        if S[i] == '0':
            dp[i+1][0] = dp[i][0]
            dp[i+1][1] = dp[i][1]
        else:
            dp[i+1][1] = dp[i][0] + dp[i][1]
            dp[i+1][1] %= MOD
        # a+b = 1
        if S[i] == '0':
            dp[i+1][1] += dp[i][1]*2
            dp[i+1][1] %= MOD
        else:
            dp[i+1][0] += dp[i][0]*2
            dp[i+1][0] %= MOD
            dp[i+1][1] += dp[i][1]*2
            dp[i+1][1] %= MOD
    print((dp[N][0]+dp[N][1]) % MOD)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, M = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    bcs = [[int(i) for i in input().split()] for _ in range(M)]
    bcs.sort(reverse=True,key=lambda c:c[1])

    ans = 0
    sel = []
    for a in A:
        if a < bcs[0][1]:
            sel.append(a)
        else:
            ans += a
    sel.sort()
    bcs = [[c] * b for b,c in bcs]
    stock = len(sel)
    from itertools import chain,zip_longest
    cnt = 0
    for a,card in zip_longest(sel,chain.from_iterable(bcs),fillvalue=0):
        if cnt == stock:
            break
        if a < card:
            ans += card
        else:
            ans += a
        cnt += 1
    print(ans)

if __name__ == "__main__":
    main()


Fixed submission:
def main():
    N, M = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    bcs = [[int(i) for i in input().split()] for _ in range(M)]
    bcs.sort(reverse=True,key=lambda c:c[1])

    ans = 0
    sel = []
    for a in A:
        if a < bcs[0][1]:
            sel.append(a)
        else:
            ans += a
    sel.sort()
    stock = len(sel)
    cards = []
    for b,c in bcs:
        cards.extend([c] * b)
        if len(cards) >= stock:
            break
    from itertools import zip_longest
    cnt = 0
    for a,card in zip_longest(sel,cards,fillvalue=0):
        if cnt == stock:
            break
        if a < card:
            ans += card
        else:
            ans += a
        cnt += 1
    print(ans)

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    from heapq import heapify,heappushpop
    N, M = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    heapify(A)
    bcs = [[int(i) for i in input().split()] for _ in range(M)]
    for i in range(M):
        for j in range(bcs[i][0]):
            heappushpop(A,bcs[i][1])
    print(sum(A))
if __name__ == "__main__":
    main()

Fixed submission:
def main():
    N, M = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    bcs = [[int(i) for i in input().split()] for _ in range(M)]
    bcs.sort(reverse=True,key=lambda c:c[1])

    ans = 0
    sel = []
    for a in A:
        if a < bcs[0][1]:
            sel.append(a)
        else:
            ans += a
    sel.sort()
    stock = len(sel)
    cards = []
    for b,c in bcs:
        cards.extend([c] * b)
        if len(cards) >= stock:
            break
    from itertools import zip_longest
    cnt = 0
    for a,card in zip_longest(sel,cards,fillvalue=0):
        if cnt == stock:
            break
        if a < card:
            ans += card
        else:
            ans += a
        cnt += 1
    print(ans)

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
import math
n = int(input())
s = [input() for i in range(n)]

ans = 0
b_pre = []
a_suf = []
ab = []
for st in s:
    if st.startswith("B") and st.endswith("A"):
        ans += st.count("AB")
        ab.append(st)
    elif st.startswith("B"):
        ans += st.count("AB")
        b_pre.append(st)
    elif st.endswith("A"):
        ans += st.count("AB")
        a_suf.append(st)
    else:
        ans += st.count("AB")

if len(b_pre) - len(a_suf) > 1:
    while len(b_pre) - len(a_suf) > 1:
        for b in b_pre:
            if b.endswith("A"):
                a_suf.append(b)
                b_pre.remove(b)
            if len(b_pre) - len(a_suf) <= 1:
                break
elif len(a_suf) - len(b_pre) > 1:
    while len(a_suf) - len(b_pre) > 1:
        for a in a_suf:
            if b.startswith("B"):
                b_pre.append(b)
                a_suf.remove(b)
            if len(a_suf) - len(b_pre) > 1:
                break

ans += math.ceil(len(ab)/2)
if len(b_pre) < len(a_suf):
    ans += len(b_pre)
    ans += len(a_suf) - len(b_pre)
else:
    ans += len(a_suf)
    ans += len(b_pre) - len(a_suf)


print(ans)

Fixed submission:
def main():
    N = int(input())
    ab_cnt = 0
    b_cnt = 0
    a_cnt = 0
    ans = 0
    for _ in range(N):
        S = input()
        ans += S.count("AB")
        if S[0] == "B" and S[-1] == "A":
            ab_cnt += 1
        elif S[0] == "B":
            b_cnt += 1
        elif S[-1] == "A":
            a_cnt += 1
    if ab_cnt > 1:
        ans += max(ab_cnt - 1, 0)
        ab_cnt = 1
    if a_cnt <= b_cnt:
        ans += a_cnt
        a_cnt = 0
        b_cnt -= a_cnt
    elif b_cnt < a_cnt:
        ans += b_cnt
        b_cnt = 0
        a_cnt -= b_cnt
    if ab_cnt > 0 and (a_cnt > 0 or b_cnt > 0):
        ans += 1
    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):

n, q = map(int,input().split())
s = input()

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

def ac_checker(s_line):
    cnt = 0
    while 'AC' in s_line:
        cnt += 1
        s_line = s_line.replace('AC','',1)
        
    return cnt

for i in range(q):
    part_s = s[(landq[i][0]-1):(landq[i][1])]
    print(ac_checker(part_s))

Fixed submission:

n, q = map(int,input().split())
s = input()

t = [0]*(n+1)
for i in range(n):
    t[i+1] = t[i] + (1 if s[i:i+2] == 'AC' else 0)

for i in range(q):
    l,r = map(int,input().split())
    print(t[r-1] - t[l-1])

Buggy python submission (verdict: Time Limit Exceeded):

n, q = map(int,input().split())
s = input()

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

def ac_checker(s_line):
    cnt = 0
    while 'AC' in s_line:
        cnt += 1
        s_line = s_line.replace('AC','',1)
        
    return cnt

for i in range(q):
    part_s = s[(landq[i][0]-1):(landq[i][1])]
    print(ac_checker(part_s))

Fixed submission:

n, q = map(int,input().split())
s = input()

t = [0]*(n+1)
for i in range(n):
    t[i+1] = t[i] + (1 if s[i:i+2] == 'AC' else 0)

for i in range(q):
    l,r = map(int,input().split())
    print(t[r-1] - t[l-1])
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    dp = [""]*(N+1)
    match = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
    for i in range(2, N+1):
        cur = (int(dp[i]) if dp[i] else 0)
        for a in A:
            if match[a] == i or (i - match[a] >= 0 and dp[i - match[a]]):
                ne = int(dp[i - match[a]] + str(a))
                if cur < ne:
                    dp[i] = str(ne)
                    cur = ne
    # print(dp)
    print(dp[N])


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    A.sort(reverse=True)
    dp = ["-"]*(N+10)
    dp[0] = ""
    match = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
    for i in range(N+1):
        if dp[i] == "-":
            continue
        for a in A:
            cur = dp[i+match[a]]
            ne = dp[i] + str(a)
            if len(cur) < len(ne) or cur < ne:
                dp[i+match[a]] = ne
    # print(dp)
    print(dp[N])


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    dp = [""]*(N+1)
    match = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
    for i in range(2, N+1):
        cur = (int(dp[i]) if dp[i] else 0)
        for a in A:
            if match[a] == i or dp[i - match[a]]:
                ne = int(dp[i - match[a]] + str(a))
                if cur < ne:
                    dp[i] = str(ne)
                    cur = ne
    # print(dp)
    print(dp[N])


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    A.sort(reverse=True)
    dp = ["-"]*(N+10)
    dp[0] = ""
    match = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
    for i in range(N+1):
        if dp[i] == "-":
            continue
        for a in A:
            cur = dp[i+match[a]]
            ne = dp[i] + str(a)
            if len(cur) < len(ne) or cur < ne:
                dp[i+match[a]] = ne
    # print(dp)
    print(dp[N])


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    N, M = (int(i) for i in input().split())
    X = [int(i) for i in input().split()]
    if N >= M: 
        print(0)
    elif N < M: 
        X.sort()
        diff = [0 for _ in range(M-1)]
        for i in range(M-1):
            diff[i] = [X[i+1] - X[i]]
        diff.sort(reverse=True)

        ans = X[-1] - X[0]
        for i in range(N-1):
            ans -= diff[i]
        print(ans)
if __name__ == "__main__":
    main()

Fixed submission:
def main():
    N, M = (int(i) for i in input().split())
    X = [int(i) for i in input().split()]
    if N >= M: 
        print(0)
    elif N < M: 
        X.sort()
        diff = [[0,0] for _ in range(M-1)]
        for i in range(M-1):
            diff[i] = [X[i+1] - X[i],i]
        diff.sort(reverse=True)
        diff = diff[:N-1]
        diff.sort(key=lambda p:p[1])

        ans = 0
        cnt = 0
        for i in range(N-1):
            ans += X[diff[i][1]] - X[cnt]
            cnt = diff[i][1] + 1
        ans += X[-1] - X[cnt]
        print(ans)
if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    # アルメリアさんを参考にした いや全然わからん
    from itertools import accumulate
    from bisect import bisect_left
    N, Q = (int(i) for i in input().split())
    A = [0] + [int(i) for i in input().split()]

    cum = [0] + [a for a in accumulate(A[1:])]
    cum_e = [e for e in accumulate(A[(1 if N & 1 else 0)::2])]

    def binary_search(x):
        ng = 0
        ok = N
        while ok - ng > 1:
            mid = ng + (ok - ng) // 2
            if A[mid] < x:
                ng = mid
            else:
                upper = N - mid + 1
                lower = mid - bisect_left(A, max(1, 2*x-A[mid])) + 1
                if upper > lower:
                    ng = mid
                else:
                    ok = mid
        return ok
    # print(cum, cum_e)
    for query in range(Q):
        x = int(input())
        ok = binary_search(x)
        ans = cum[N] - cum[ok-1]
        t = N - (N-ok+1)*2
        # print(ok, t)
        if t > 0:
            ans += cum_e[t//2]
        print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    # アルメリアさんを参考にした いや全然わからん
    from itertools import accumulate
    from bisect import bisect_left
    import sys
    input = sys.stdin.buffer.readline
    N, Q = (int(i) for i in input().split())
    A = [0] + [int(i) for i in input().split()]

    cum = [0] + [a for a in accumulate(A[1:])]
    cum_e = [e for e in accumulate(A[(1 if N & 1 else 0)::2])]

    def binary_search(x):
        ng = 0
        ok = N
        while ok - ng > 1:
            mid = ng + (ok - ng) // 2
            if A[mid] < x:
                ng = mid
            else:
                upper = N - mid + 1
                lower = mid - bisect_left(A, max(1, 2*x-A[mid])) + 1
                if upper > lower:
                    ng = mid
                else:
                    ok = mid
        return ok
    # print(cum, cum_e)
    for query in range(Q):
        x = int(input())
        ok = binary_search(x)
        ans = cum[N] - cum[ok-1]
        t = N - (N-ok+1)*2
        # print(ok, t)
        if t > 0:
            ans += cum_e[t//2]
        print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int,input().split())
h = list(map(int,input().split()))

dp = [float("inf")] * n
dp[0] = 0

for i in range(n-1):
    for j in range(1,k+1):
        if i+j <= n-1:
            dp[i+j] = min(dp[i] + abs(h[i] - h[i+j]), dp[i+j])
print(dp[n-1])

Fixed submission:

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

dp = [float("inf")]*N 
dp[0] = 0

for i in range(N):
    for k in range(1,K+1):
        if i+k < N:
            dp[i+k] = min(dp[i+k],abs(h[i] - h[i+k]) + dp[i])

print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import sys
    input = sys.stdin.readline
    N, W = (int(i) for i in input().split())
    weight = [0] * (N+1)
    value = [0] * (N+1)
    for i in range(1, N+1):
        w, v = (int(i) for i in input().split())
        weight[i] = w
        value[i] = v
    memo = [[-1] * (W + 1) for _ in range(N + 1)]

    def rec(i, w):
        if i == 0:
            return 0
        if memo[i][w] != -1:
            return memo[i][w]
        res = 0
        if w - weight[i] >= 0:
            res = max(rec(i-1, w), rec(i-1, w-weight[i])+value[i])
        else:
            res = rec(i-1, w)
        memo[i][w] = res
        return res

    print(rec(N, W))


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    N, W = (int(i) for i in input().split())
    weight = [0] * (N+1)
    value = [0] * (N+1)
    for i in range(1, N+1):
        w, v = (int(i) for i in input().split())
        weight[i] = w
        value[i] = v
    dp = [[0 for i in range(W + 1)] for j in range(N + 1)]

    for i in range(1, N+1):
        for w in range(W+1):
            if w - weight[i] >= 0:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])
            else:
                dp[i][w] = dp[i-1][w]

    print(dp[N][W])


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, W = (int(i) for i in input().split())
    weight = [0] * (N+1)
    value = [0] * (N+1)
    for i in range(1, N+1):
        w, v = (int(i) for i in input().split())
        weight[i] = w
        value[i] = v
    memo = [[-1 for i in range(W + 1)] for j in range(N + 1)]

    def rec(i, w):
        if i == 0:
            return 0
        if memo[i][w] != -1:
            return memo[i][w]
        res = 0
        if w - weight[i] >= 0:
            res = max(rec(i-1, w), rec(i-1, w-weight[i])+value[i])
        else:
            res = rec(i-1, w)
        memo[i][w] = res
        return res

    print(rec(N, W))


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    N, W = (int(i) for i in input().split())
    weight = [0] * (N+1)
    value = [0] * (N+1)
    for i in range(1, N+1):
        w, v = (int(i) for i in input().split())
        weight[i] = w
        value[i] = v
    dp = [[0 for i in range(W + 1)] for j in range(N + 1)]

    for i in range(1, N+1):
        for w in range(W+1):
            if w - weight[i] >= 0:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])
            else:
                dp[i][w] = dp[i-1][w]

    print(dp[N][W])


if __name__ == '__main__':
    main()