Problem p03732 (python)

Fixed submission:


def main():
    num, max_weigh = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(num)]

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

    pre_data = data[0][0]
    pre_ind = 0
    for i in range(num):
        if pre_data != data[i][0]:
            split_data.append(data[pre_ind:i])
            pre_data = data[i][0]
            pre_ind = i
    split_data.append(data[pre_ind:num])

    while len(split_data) != 4:
        split_data.append([])

    ans = 0

    for i in range(-1, len(split_data[0])):
        if i == -1:
            sum_i = 0
            sum_i_w = 0
        else:
            sum_i += split_data[0][i][1]
            sum_i_w += split_data[0][i][0]
        if sum_i_w > max_weigh:
            break
        ans = max(ans, sum_i)

        for j in range(-1, len(split_data[1])):
            if j == -1:
                sum_j = 0
                sum_j_w = 0
            else:
                sum_j += split_data[1][j][1]
                sum_j_w += split_data[1][j][0]
            if sum_i_w + sum_j_w > max_weigh:
                break
            ans = max(ans, sum_i + sum_j)

            for k in range(-1, len(split_data[2])):
                if k == -1:
                    sum_k = 0
                    sum_k_w = 0
                else:
                    sum_k += split_data[2][k][1]
                    sum_k_w += split_data[2][k][0]
                if sum_i_w + sum_j_w + sum_k_w > max_weigh:
                    break
                ans = max(ans, sum_i + sum_j + sum_k)

                for l in range(-1, len(split_data[3])):
                    if l == -1:
                        sum_l = 0
                        sum_l_w = 0
                    else:
                        sum_l += split_data[3][l][1]
                        sum_l_w += split_data[3][l][0]
                    if sum_i_w + sum_j_w + sum_k_w + sum_l_w > max_weigh:
                        break
                    ans = max(ans, sum_i + sum_j + sum_k + sum_l)

    print(ans)



if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):


def main():
    num, max_weigh = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(num)]
    kosuu = [0, 0, 0, 0]
    start_weigh = data[0][0]
    for i in range(num):
        weigh, value = data[i]
        kosuu[weigh -  start_weigh] += 1

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

    j_ind, k_ind, l_ind = num, num, num

    for i in range(num):
        if data[i][0] == start_weigh + 1:
            j_ind = i
            break
    for i in range(j_ind + 1,  num):
        if data[i][0] == start_weigh + 2:
            k_ind = i
            break

    for i in range(k_ind + 1, num):
        if data[i][0] == start_weigh + 3:
            k_ind = i
            break

    # print(data)
    # print(start_weigh)
    # print(j_ind, k_ind, l_ind)
    # print(kosuu)


    i_sum, j_sum, k_sum, l_sum = 0, 0, 0, 0
    i_sum_w, j_sum_w, k_sum_w, l_sum_w = 0, 0, 0, 0

    ans = 0

    for i in range(-1, kosuu[0]):
        if i == -1:
            i_sum = 0
            i_sum_w = 0
        else:
            i_sum += data[i][1]
            i_sum_w += data[i][0]

        if sum([i_sum_w]) > max_weigh:
            break

        ans = max(ans, i_sum)

        # print('i', i_sum_w)

        for j in range(j_ind - 1, j_ind + kosuu[1]):
            if j == j_ind - 1:
                j_sum = 0
                j_sum_w = 0
            else:
                j_sum += data[j][1]
                j_sum_w += data[j][0]

            # print(i_sum_w, j_sum_w, 'uuu')
            if sum([i_sum_w, j_sum_w]) > max_weigh:
                break
            ans = max(ans, i_sum + j_sum)
            # print('j', j_sum_w)

            for k in range(k_ind - 1, k_ind + kosuu[2]):
                if k == k_ind - 1:
                    k_sum = 0
                    k_sum_w = 0
                else:
                    k_sum += data[k][1]
                    k_sum_w += data[k][0]

                # print(i_sum_w, j_sum_w, k_sum_w, ans, k)


                if sum([i_sum_w, j_sum_w, k_sum_w]) > max_weigh:
                    break

                ans = max(ans, i_sum + j_sum + k_sum)

                for l in range(l_ind, l_ind + kosuu[3]):
                    if l == l_ind - 1:
                        l_sum = 0
                        l_sum_w = 0
                    else:
                        l_sum += data[l][1]
                        l_sum_w += data[l][0]

                    if sum([i_sum_w, j_sum_w, k_sum_w, l_sum_w]) > max_weigh:
                        break

                    ans = max(ans, i_sum + j_sum + k_sum + l_sum)

    print(ans)







if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):


import numpy as np
import sys
input = sys.stdin.readline

N, W = map(int, input().split())
dp = np.full(N * 1000 + 1, 10 ** 10, dtype=np.int64)

dp[0] = 0
for _ in range(N):
    w, v = map(int, input().split())
    np.minimum(dp[:-v] + w, dp[v:], out=dp[v:])
print(((dp <= W) * np.arange(N * 1000 + 1)).max())