Problem:


Score : 400 points

Problem Statement

You have N items and a bag of strength W.
The i-th item has a weight of w_i and a value of v_i.

You will select some of the items and put them in the bag.
Here, the total weight of the selected items needs to be at most W.

Your objective is to maximize the total value of the selected items.

Constraints

1 ≤ N ≤ 100

1 ≤ W ≤ 10^9

1 ≤ w_i ≤ 10^9

For each i = 2,3,...,N, w_1 ≤ w_i ≤ w_1 + 3.

1 ≤ v_i ≤ 10^7

W, each w_i and v_i are integers.

Input

Input is given from Standard Input in the following format:

N W
w_1 v_1
w_2 v_2
:
w_N v_N

Output

Print the maximum possible total value of the selected items.

Sample Input 1

4 6
2 1
3 4
4 10
3 4

Sample Output 1

11

The first and third items should be selected.

Sample Input 2

4 6
2 1
3 7
4 10
3 6

Sample Output 2

13

The second and fourth items should be selected.

Sample Input 3

4 10
1 100
1 100
1 100
1 100

Sample Output 3

400

You can take everything.

Sample Input 4

4 1
10 100
10 100
10 100
10 100

Sample Output 4

0

You can take nothing.



Sample input:
4 6
2 1
3 4
4 10
3 4


Sample output:
11

Submission status: Runtime Error

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


def gcd(n, m):
    if n % m == 0:
        return m
    else:
        return gcd(m, n % m)


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


def lcm(n, m):
    return (n * m) // gcd(n, m)


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v


# Width First Search (+ Distance)
def wfs_d(D, N, K):
    """
    D: 隣接行列(距離付き)
    N: ノード数
    K: 始点ノード
    """

    dfk = [-1] * (N + 1)
    dfk[K] = 0

    cps = [(K, 0)]
    r = [False] * (N + 1)
    r[K] = True
    while len(cps) != 0:
        n_cps = []
        for cp, cd in cps:
            for i, dfcp in enumerate(D[cp]):
                if dfcp != -1 and not r[i]:
                    dfk[i] = cd + dfcp
                    n_cps.append((i, cd + dfcp))
                    r[i] = True

        cps = n_cps[:]

    return dfk


# Depth First Search (+Distance)
def dfs_d(v, pre, dist):
    """
    v:  現在のノード
    pre: １つ前のノード
    dist: 現在の距離

    以下は別途用意する
    D: 隣接リスト(行列ではない)
    D_dfs_d: dfs_d関数で用いる，始点ノードから見た距離リスト
    """

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return


def sigma(N):
    ans = 0
    for i in range(1, N + 1):
        ans += i
    return ans


def comb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def bisearch(L, target):
    low = 0
    high = len(L) - 1
    
    while low <= high:
        mid = (low + high) // 2
        guess = L[mid]
        if guess == target:
            return True
        elif guess < target:
            low = mid + 1
        elif guess > target:
            high = mid - 1
    if guess != target:
        return False

# --------------------------------------------

dp = None


def main():
    N, W = li_input()
    A = [li_input() for _ in range(N)]  # w,v

    dp = [[0] * (W + 1) for _ in range(N)]
    
    for i in range(W + 1):
        if A[0][0] <= i:
            dp[0][i] = A[0][1]

    for i in range(1, N):
        for j in range(W + 1):
            weight, value = A[i][0], A[i][1]

            if j - weight >= 0:
                dp[i][j] = max(
                    dp[i - 1][j],
                    dp[i-1][j-weight] + value
                )
            else:
                dp[i][j] = dp[i-1][j]

    # for d in dp:
    #     print(d)

    print(max(dp[-1]))

main()

Submission status: Runtime Error

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


def gcd(n, m):
    if n % m == 0:
        return m
    else:
        return gcd(m, n % m)


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


def lcm(n, m):
    return (n * m) // gcd(n, m)


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v


# Width First Search (+ Distance)
def wfs_d(D, N, K):
    """
    D: 隣接行列(距離付き)
    N: ノード数
    K: 始点ノード
    """

    dfk = [-1] * (N + 1)
    dfk[K] = 0

    cps = [(K, 0)]
    r = [False] * (N + 1)
    r[K] = True
    while len(cps) != 0:
        n_cps = []
        for cp, cd in cps:
            for i, dfcp in enumerate(D[cp]):
                if dfcp != -1 and not r[i]:
                    dfk[i] = cd + dfcp
                    n_cps.append((i, cd + dfcp))
                    r[i] = True

        cps = n_cps[:]

    return dfk


# Depth First Search (+Distance)
def dfs_d(v, pre, dist):
    """
    v:  現在のノード
    pre: １つ前のノード
    dist: 現在の距離

    以下は別途用意する
    D: 隣接リスト(行列ではない)
    D_dfs_d: dfs_d関数で用いる，始点ノードから見た距離リスト
    """

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return


def sigma(N):
    ans = 0
    for i in range(1, N + 1):
        ans += i
    return ans


def comb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def bisearch(L, target):
    low = 0
    high = len(L) - 1
    
    while low <= high:
        mid = (low + high) // 2
        guess = L[mid]
        if guess == target:
            return True
        elif guess < target:
            low = mid + 1
        elif guess > target:
            high = mid - 1
    if guess != target:
        return False

# --------------------------------------------

dp = None


def main():
    N, W = li_input()
    A_ = [li_input() for _ in range(N)]

    A = []
    for a in A_:
        if a[0] <= W:
            A.append(a)

    if len(A) == 0:
        print(0)
        return

    dp = [[0] * (W + 1) for _ in range(N)]

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

    print(max(dp[-1]))


main()

Submission status: Runtime Error

Solution code:
#import sys
#stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

from itertools import accumulate

n,w = li()
wi,vi = li()
w0 = wi
v_list = [[0] for _ in range(4)]
v_list[0].append(vi)

for _ in range(n-1):
    wi,vi = li()
    v_list[wi-w0].append(vi)
    
for i in range(4):
    v_list[i].sort(reverse=True)
    v_list[i] = list(accumulate(v_list[i]))
    
ans = 0
res = w
for w1 in range(len(v_list[0])):
    
    if w - w0*(w1) < 0:
        pass
    else:
        res1 = w - w0*(w1)
        ans1 = v_list[0][w1]
        ans = max(ans, ans1)
    

    for w2 in range(len(v_list[1])):

        if res1 - (w0+1)*(w2) < 0:
            pass
        
        else:
            res2 = res1 - (w0+1)*(w2)
            ans2 = ans1 + v_list[1][w2]
            ans = max(ans, ans2)

        
        
        for w3 in range(len(v_list[2])):
            
            if res2 - (w0+2)*(w3) < 0:
                pass
            
            else:
                res3 = res2 - (w0+2)*(w3)
                ans3 = ans2 + v_list[2][w3]
                ans = max(ans, ans3)
                
            
            for w4 in range(len(v_list[3])):

                if res3 - (w0+3)*(w4) < 0:
                    pass
                
                else:
                    res4 = res3 - (w0+3)*(w4)
                    ans4 = ans3 + v_list[3][w4]
                    ans = max(ans, ans4)

                
print(ans)

Submission status: Runtime Error

Solution code:
n, wm = list(map(int, input().split()))
w = []
v = []
for i in range(n):
    vw = list(map(int, input().split()))
    w.append(vw[0])
    v.append(vw[1]) 
    
dp = [[0]*(wm+1) for _ in range(n+1)]
for i in range(n):
    for j in range(wm+1):
        if j >= w[i]:
            dp[i+1][j] = max([dp[i][j], dp[i][j-w[i]]+v[i]])
        else:
            dp[i+1][j] = dp[i][j]
print(dp[n][wm])

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
P = []
for i in range(N):
  P.append(list(map(int, input().split())))

#dp[i][w] : i番目までの品物で、wの重みでできる最大の価値. 1-indexed
dp = [[0] * (W+1) for i in range(N+1)]

for i in range(1,N+1):
  weight = P[i-1][0]
  value = P[i-1][1]

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

#print(dp)
print(max(dp[N][:]))

Submission status: Runtime Error

Solution code:

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, W, WV):
    items = defaultdict(list)
    for w, v in WV:
        items[w].append(v)

    for w in items:
        items[w].sort(reverse=True)

    for i in range(4-len(items)):
        items[-i] = []
    ws = list(items.keys())

    @lru_cache(maxsize=None)
    def f(rw, i, j, k, l):
        ret = 0
        if ws[0] <= rw and i < len(items[ws[0]]):
            ret = max(ret, f(rw - ws[0], i+1, j, k, l) + items[ws[0]][i])
        if ws[1] <= rw and j < len(items[ws[1]]):
            ret = max(ret, f(rw - ws[1], i, j+1, k, l) + items[ws[1]][j])
        if ws[2] <= rw and k < len(items[ws[2]]):
            ret = max(ret, f(rw - ws[2], i, j, k+1, l) + items[ws[2]][k])
        if ws[3] <= rw and k < len(items[ws[3]]):
            ret = max(ret, f(rw - ws[3], i, j, k, l+1) + items[ws[3]][l])

        return ret

    return f(W, 0, 0, 0, 0)


def main():
    N, W = read_int_n()
    WV = [read_int_n() for _ in range(N)]

    print(slv(N, W, WV))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

N,W = map(int, input().split())
wN = []
vN = []
for i in range(N):
    w,v = map(int, input().split())
    wN.append(w)
    vN.append(v)

dp = [[0] * (3*(N-1)+100) for i in range(N+1)]

# 答えが明らかな範囲はDPに含めない
if W < wN[0]:
    print(0)
    exit()
elif W >= sum(wN):
    print(sum(vN))
    exit()

# wNの範囲はかなり限定されているので、オフセットを用意
# (-1するのは0地点を残すため)
offset = wN[0]-1
W -= offset

for i in range(N):
    for j in range(offset, (3*(N-1)+100) + offset):

        if wN[i] <= j:
            # max(0,～)で0未満を探しに行くのを避ける
            dp[i+1][j-offset] = max(dp[i][max(0,j-wN[i]-offset)] + vN[i], dp[i][j-offset])
        else:
            dp[i+1][j-offset] = dp[i][j-offset]

print(dp[N][W])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

N,W = map(int, input().split())
wN = []
vN = []
for i in range(N):
    w,v = map(int, input().split())
    wN.append(w)
    vN.append(v)

dp = [[0] * (3*(N-1)+1)+100 for i in range(N+1)]

# 答えが明らかな範囲はDPに含めない
if W < wN[0]:
    print(0)
    exit()
elif W >= sum(wN):
    print(sum(vN))
    exit()

# wNの範囲はかなり限定されているので、オフセットを用意
# (-1するのは0地点を残すため)
offset = wN[0]-1
W -= offset

for i in range(N):
    for j in range(offset, (3*(N-1)+1)+100 + offset):

        if wN[i] <= j:
            # max(0,～)で0未満を探しに行くのを避ける
            dp[i+1][j-offset] = max(dp[i][max(0,j-wN[i]-offset)] + vN[i], dp[i][j-offset])
        else:
            dp[i+1][j-offset] = dp[i][j-offset]

print(dp[N][W])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

N,W = map(int, input().split())
wN = []
vN = []
for i in range(N):
    w,v = map(int, input().split())
    wN.append(w)
    vN.append(v)

dp = [[0] * (3*(N-1)+1)*100 for i in range(N+1)]

# 答えが明らかな範囲はDPに含めない
if W < wN[0]:
    print(0)
    exit()
elif W >= sum(wN):
    print(sum(vN))
    exit()

# wNの範囲はかなり限定されているので、オフセットを用意
# (-1するのは0地点を残すため)
offset = wN[0]-1
W -= offset

for i in range(N):
    for j in range(offset, (3*(N-1)+1)*100 + offset):

        if wN[i] <= j:
            # max(0,～)で0未満を探しに行くのを避ける
            dp[i+1][j-offset] = max(dp[i][max(0,j-wN[i]-offset)] + vN[i], dp[i][j-offset])
        else:
            dp[i+1][j-offset] = dp[i][j-offset]

print(dp[N][W])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

N,W = map(int, input().split())
wN = []
vN = []
for i in range(N):
    w,v = map(int, input().split())
    wN.append(w)
    vN.append(v)

dp = [[0] * (3*(N-1)+1) for i in range(N+1)]

# 答えが明らかな範囲はDPに含めない
if W < wN[0]:
    print(0)
    exit()
elif W >= sum(wN):
    print(sum(vN))
    exit()

# wNの範囲はかなり限定されているので、オフセットを用意
# (-1するのは0地点を残すため)
offset = wN[0]-1
W -= offset

for i in range(N):
    for j in range(offset, 3*(N-1)+1 + offset):

        if wN[i] <= j:
            # max(0,～)で0未満を探しに行くのを避ける
            dp[i+1][j-offset] = max(dp[i][max(0,j-wN[i]-offset)] + vN[i], dp[i][j-offset])
        else:
            dp[i+1][j-offset] = dp[i][j-offset]

print(dp[N][W])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

N,W = map(int, input().split())
wN = []
vN = []
for i in range(N):
    w,v = map(int, input().split())
    wN.append(w)
    vN.append(v)

dp = [[0] * (wN[0]+3)*N for i in range(N+1)]

if W < wN[0]:
    print(0)
    exit()
elif W >= (wN[0]+3)*N:
    print(sum(vN))
    exit()

# wNの範囲はかなり限定されているので、オフセットを用意
# (-1するのは0地点を残すため)
offset = wN[0]-1
W -= offset

for i in range(N):
    for j in range(offset, (wN[0]+3)*N + offset):

        if wN[i] <= j:
            # max(0,～)で0未満を探しに行くのを避ける
            dp[i+1][j-offset] = max(dp[i][max(0,j-wN[i]-offset)] + vN[i], dp[i][j-offset])
        else:
            dp[i+1][j-offset] = dp[i][j-offset]

print(dp[N][W])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

N,W = map(int, input().split())
wN = []
vN = []
for i in range(N):
    w,v = map(int, input().split())
    wN.append(w)
    vN.append(v)

dp = [[0] * (wN[0]+3)*N for i in range(N+1)]

if W < wN[0]:
    print(0)
    exit()
elif W >= (wN[0]+3)*N:
    print(sum(vN))

# wNの範囲はかなり限定されているので、オフセットを用意
# (-1するのは0地点を残すため)
offset = wN[0]-1
W -= offset

for i in range(N):
    for j in range(offset, (wN[0]+3)*N + offset):

        if wN[i] <= j:
            # max(0,～)で0未満を探しに行くのを避ける
            dp[i+1][j-offset] = max(dp[i][max(0,j-wN[i]-offset)] + vN[i], dp[i][j-offset])
        else:
            dp[i+1][j-offset] = dp[i][j-offset]

print(dp[N][W])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

N,W = map(int, input().split())
wN = []
vN = []
for i in range(N):
    w,v = map(int, input().split())
    wN.append(w)
    vN.append(v)

dp = [[0] * ((wN[0]+3)*N - 3) for i in range(N+1)]

if W < wN[0]:
    print(0)
    exit()
elif W >= (wN[0]+3)*N - 3:
    print(sum(vN))

# wNの範囲はかなり限定されているので、オフセットを用意
# (-1するのは0地点を残すため)
offset = wN[0]-1
W -= offset

for i in range(N):
    for j in range(offset, (wN[0]+3)*N - 3 + offset):

        if wN[i] <= j:
            # max(0,～)で0未満を探しに行くのを避ける
            dp[i+1][j-offset] = max(dp[i][max(0,j-wN[i]-offset)] + vN[i], dp[i][j-offset])
        else:
            dp[i+1][j-offset] = dp[i][j-offset]

print(dp[N][W])

Submission status: Runtime Error

Solution code:
'''
https://beta.atcoder.jp/contests/abc060/tasks/arc073_://beta.atcoder.jp/contests/abc060/tasks/arc073_b
'''


n,w_limit = map(int,input().split(" "))
#n, w_limit = nw[0], nw[1]
item_list = []
for i in range(n):
  item_list.append(list(map(int,input().split(" "))))
#dpテーブルの作成
dp = [[0] * (w_limit + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    item_weight,item_value = item_list[i - 1]
    for w in range(1, w_limit + 1):
        if w - item_weight >= 0:
            dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - item_weight] + item_value)
        else:
            dp[i][w] = dp[i - 1][w]

print(max(dp[-1]))

Submission status: Runtime Error

Solution code:
'''
https://beta.atcoder.jp/contests/abc060/tasks/arc073_://beta.atcoder.jp/contests/abc060/tasks/arc073_b
'''


n,w_limit = map(int,input().split(" "))
#n, w_limit = nw[0], nw[1]
item_list = [list(map(int,input().split(" "))) for _ in range(n)]
#dpテーブルの作成
dp = [[0] * (w_limit + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    item_weight,item_value = item_list[i - 1]
    for w in range(1, w_limit + 1):
        if w - item_weight >= 0:
            dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - item_weight] + item_value)
        else:
            dp[i][w] = dp[i - 1][w]

print(max(dp[-1]))

Submission status: Runtime Error

Solution code:
'''
https://beta.atcoder.jp/contests/abc060/tasks/arc073_://beta.atcoder.jp/contests/abc060/tasks/arc073_b
'''


n,w_limit = map(int,input().split(" "))
#n, w_limit = nw[0], nw[1]
item_list = [[list(map(int,input().split(" ")))] for _ in range(n)]
#dpテーブルの作成
dp = [[0] * (w_limit + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    item_weight,item_value = item_list[i - 1]
    for w in range(1, w_limit + 1):
        if w - item_weight >= 0:
            dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - item_weight] + item_value)
        else:
            dp[i][w] = dp[i - 1][w]

print(max(dp[-1]))

Submission status: Runtime Error

Solution code:
'''
https://beta.atcoder.jp/contests/abc060/tasks/arc073_://beta.atcoder.jp/contests/abc060/tasks/arc073_b
'''

nw = [int(i) for i in input().split()]
n, w_limit = nw[0], nw[1]
item_list = [[int(i) for i in input().split()] for _ in range(n)]

#dpテーブルの作成
dp = [[0] * (w_limit + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    item_weight = item_list[i - 1][0]
    item_value = item_list[i - 1][1]
    for w in range(1, w_limit + 1):
        if w - item_weight >= 0:
            dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - item_weight] + item_value)
        else:
            dp[i][w] = dp[i - 1][w]

print(max(dp[-1]))

Submission status: Runtime Error

Solution code:
nw = [int(i) for i in input().split()]
n, w_limit = nw[0], nw[1]
item_list = [[int(i) for i in input().split()] for _ in range(n)]

#dpテーブルの作成
dp = [[0] * (w_limit + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    item_weight = item_list[i - 1][0]
    item_value = item_list[i - 1][1]
    for w in range(1, w_limit + 1):
        if w - item_weight >= 0:
            dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - item_weight] + item_value)
        else:
            dp[i][w] = dp[i - 1][w]

print(max(dp[-1]))

Submission status: Runtime Error

Solution code:
nw = [int(i) for i in input().split()]
n, w_limit = nw[0], nw[1]
item_list = [[int(i) for i in input().split()] for _ in range(n)]

#dpテーブルの作成
dp = [[0] * (w_limit + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    item_weight = item_list[i - 1][0]
    item_value = item_list[i - 1][1]
    for w in range(1, w_limit + 1):
        if w - item_weight >= 0:
            dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - item_weight] + item_value)
        else:
            dp[i][w] = dp[i - 1][w]

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

Submission status: Runtime Error

Solution code:
n,m=input().split()
N = int(n)
M = int(m)
w_list = []
v_list = []
w1_values = []
w2_values = []
w3_values = []
w4_values = []
sum_w1_values = []
sum_w2_values = []
sum_w3_values = []
sum_w4_values = []
sum_v1 = 0
sum_v2 = 0
sum_v3 = 0
sum_v4 = 0

for i in range(N):
	w,v = input().split()
	w = int(w)
	v = int(v)
	w_list.append(w)
	v_list.append(v)

w1 = w_list[0]
for j in range(N):
	if(w_list[j] == w1):
		w1_values.append(v_list[j])
		sum_v1 += v_list[j]
		sum_w1_values.append(sum_v1)

	elif(w_list[j] == w1+1):
		w2_values.append(v_list[j])
		sum_v2 += v_list[j]
		sum_w2_values.append(sum_v2)

	elif(w_list[j] == w1+2):
		w3_values.append(v_list[j])
		sum_v3 += v_list[j]
		sum_w3_values.append(sum_v3)

	elif(w_list[j] == w1+3):
		w4_values.append(v_list[j])
		sum_v4 += v_list[j]
		sum_w4_values.append(sum_v4)

w1_values.sort()
w1_values.reverse()
w2_values.sort()
w2_values.reverse()
w3_values.sort()
w3_values.reverse()
w4_values.sort()
w4_values.reverse()

for p in range(len(w1_values)):
	sum_v1 += w1_values[p]
	sum_w1_values.append(sum_v1)

for q in range(len(w2_values)):
	sum_v2 += w2_values[q]
	sum_w2_values.append(sum_v2)

for r in range(len(w3_values)):
	sum_v3 += w3_values[r]
	sum_w3_values.append(sum_v3)

for s in range(len(w4_values)):
	sum_v4 += w1_values[s]
	sum_w4_values.append(sum_v4)


sum_w1_values.insert(0,0)
sum_w2_values.insert(0,0)
sum_w3_values.insert(0,0)
sum_w4_values.insert(0,0)

max_value = 0
count = 0
for w in range(len(sum_w4_values)):
	for x in range(len(sum_w3_values)):
		for y in range(len(sum_w2_values)):
			for z in range(len(sum_w1_values)):
				count = w+x+y+z
				weight = (w1)*z + (w1+1)*y +(w1+2)*x + (w1+3)*w
				if(count<=N and weight<=M and max_value<(sum_w1_values[z] + sum_w2_values[y] + sum_w3_values[x] + sum_w4_values[w])):
					max_value = sum_w1_values[z] + sum_w2_values[y] + sum_w3_values[x] + sum_w4_values[w]


print(max_value)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
N, W = map(int, input().split())
dd = defaultdict(int)
dd[0] = 0
for i in range(N):
    w, v = map(int, input().split())
    ddOld = dd.copy()
    for dk, dv in ddOld.items():
        dd[dk+w] = max(ddOld[dk+w], ddOld[dk]+v)
ans = 0
for dk, dv in dd.items():
    if dk <= W:
        ans = max(ans, dv)
print(ans)

Submission status: Runtime Error

Solution code:
N,W = map(int,input().split())
w_in, v = map(int,input().split())
table = [[] for i in range(4)]
table[0].append(v)
for i in range(N-1):
    w, v = map(int,input().split())
    table[w-w_in].append(v)
for i in range(N):
    table[i].sort(reverse=True)
    for j in range(len(table[i])-1):
            table[i][j+1] += table[i][j]
    table[i].insert(0,0)
ans = 0
for i in range(len(table[0])):
    for j in range(len(table[1])):
        for k in range(len(table[2])):
            for l in range(len(table[3])):
                if w_in*i+(w_in+1)*j+(w_in+2)*k+(w_in+3)*l <= W:
                    ans = max(ans, table[0][i]+table[1][j]+table[2][k]+table[3][l])
print(ans)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#define REP(i,n) for (long i=0;i<(n);i++)
#define FOR(i,a,b) for (long i=(a);i<(b);i++)
#define RREP(i,n) for(long i=n;i>=0;i--)
#define RFOR(i,a,b) for(long i=(a);i>(b);i--)
#define dump1d_arr(array) REP(i,array.size()) cerr << #array << "[" << (i) << "] ==> " << (array[i]) << endl;
#define dump2d_arr(array) REP(i,array.size()) REP(j,array[i].size()) cerr << #array << "[" << (i) << "]" << "[" << (j) << "] ==> " << (array[i][j]) << endl;
#define dump(x)  cerr << #x << " => " << (x) << endl;
#define CLR(vec) { REP(i,vec.size()) vec[i] = 0; } 
#define llINF (long long) 9223372036854775807
#define loINF (long) 2147483647
#define shINF (short) 32767
#define SORT(c) sort((c).begin(),(c).end())

using namespace std;
typedef vector<long> VI;
typedef vector<VI> VVI;

int main(void){
	long N,W;
	cin >> N >> W;
	VI w(N),v(N);

	REP(i,N){
		cin >> w[i] >> v[i];
	}

	VVI dp(N+1,VI(W+1,0));

	FOR(i,1,N+1){
		FOR(j,1,W+1){
			if (j - w[i-1] < 0) dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
			else dp[i][j] = max({dp[i-1][j - w[i-1]] + v[i-1],dp[i][j-1],dp[i-1][j]});
		}
	}

	//dump2d_arr(dp);

	cout << dp[N][W] << endl;

	return 0;
}

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
https://abc060.contest.atcoder.jp/tasks/arc073_b
01ナップサック問題
Wの上限値が非常に大きいケース(～1e9)。Wを横軸にしてdpテーブルを作成すると非常に大きくなってしまうので、メモリ消費や処理時間が問題になる。
価値に対する重さが最小になるようにdpを計算する
"""
import sys
from sys import stdin
input = stdin.readline
from collections import namedtuple
from operator import itemgetter
from bisect import bisect_right


def solve(items, W, max_v):
    # 表を上から組み立てていく方式
    n = len(items)
    dp = [[float('inf')]*(n*max_v + 1) for _ in range(n+1)] #  横軸が で縦軸が の種類
    dp[0][0] = 0

    for i, item in enumerate(items):
        for j in range(n * max_v + 1):
            if j < item.value:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = min(dp[i][j], dp[i][j-item.value]+item.weight)

    for j in range(n * max_v + 1):
        if dp[n][j] <= W:
            result = j
    return result

    # dpテーブル値は基本的に右にいくほど増加するが、infが入っているセルがあるのでbinsectは使用できない
    # result = bisect_right(dp[n], W)
    # return result-1

item = namedtuple('item', ['weight', 'value'])
def main(args):
    # items = [item(2, 3), item(1, 2), item(3, 4), item(2, 2)]
    N, W = map(int, input().split())
    items = []
    for _ in range(N):
        w, v = map(int, input().split())
        items.append(item(w, v))
    max_v = max(items, key=itemgetter(1)).value #  items内で最大のvalueを持つ項目を探し、そのアイテムのvalue値をゲットする

    result = solve(items, W, max_v)
    print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
w, v = [0] * N, [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())
minW = min(w)
for i in range(N):
    w[i] -= minW
MAX_W = 3 * 100
MAX_V = int(1e9)
INF = MAX_V + 2
dp = [[-INF] * (MAX_W + 10) for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(MAX_W, -1, -1):
        for k in range(N-1, -1, -1):
            dp[k+1][j+w[i]] = max((dp[k+1][j+w[i]], dp[k][j] + v[i]))

ans = 0
for i in range(N+1):
    for j in range(i * MAX_W + 1):
        if i * minW + j <= W:
            # print('i * minW: %d, j: %d, dp: %d' % (i*minW, j, dp[i][j]))
            ans = max((ans, dp[i][j]))

print(ans)

Submission status: Runtime Error

Solution code:
import heapq
N,W=map(int,raw_input().split())
wv=[]

w_sum=0
for i in range(N):
	w,v=map(int,raw_input().split())
	w_sum+=w
	wv.append((w,v))


a=[ float("-inf") for i in range(w_sum+1) ]


q=[]
for ind_i, i in enumerate(wv):
	w=i[0]
	v=i[1]
	#Initialize
	if ind_i==0:
		a[0]=0
		a[w]=v
		continue

	#Put queue
	for ind_j, j in enumerate(a):
		if j!=float("-inf"):
			heapq.heappush(q,(ind_j,j))
	
	while len(q)!=0:
		ind_j, j=heapq.heappop(q)
		a[ind_j+w]=max(a[ind_j+w], a[ind_j]+v)


print max(a[:W+1])

Submission status: Runtime Error

Solution code:
import heapq
N,W=map(int,raw_input().split())
wv=[]

w_sum=0
for i in range(N):
	w,v=map(int,raw_input().split())
	w_sum+=w
	wv.append((w,v))


a=[ float("-inf") for i in range(w_sum*2) ]

i=0
i=1
q=[]
for ind_i, i in enumerate(wv):
	w=i[0]
	v=i[1]
	#Initialize
	if ind_i==0:
		a[0]=0
		a[w]=v
		continue
	#Put queue
	for ind_j, j in enumerate(a):
		if j!=float("-inf"):
			heapq.heappush(q,(ind_j,j))
	
	while len(q)!=0:
		ind_j, j=heapq.heappop(q)
		a[ind_j+w]=max(a[ind_j+w], a[ind_j]+v)
		
print max(a[:W+1])

Submission status: Runtime Error

Solution code:
import heapq
N,W=map(int,raw_input().split())
wv=[]

w_sum=0
for i in range(N):
	w,v=map(int,raw_input().split())
	w_sum+=w
	wv.append((w,v))


a=[ float("-inf") for i in range(w_sum+1) ]

i=0
i=1
q=[]
for ind_i, i in enumerate(wv):
	w=i[0]
	v=i[1]
	#Initialize
	if ind_i==0:
		a[0]=0
		a[w]=v
		continue
	#Put queue
	for ind_j, j in enumerate(a):
		if j!=float("-inf"):
			heapq.heappush(q,(ind_j,j))
	
	while len(q)!=0:
		ind_j, j=heapq.heappop(q)
		a[ind_j+w]=max(a[ind_j+w], a[ind_j]+v)
		

print max(a[:W+1])

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
w, v = [0] * N, [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())

minW = min(w)
for i in range(N):
    w[i] -= minW

INF = int(1e9)
dp = [[-INF] * (3 * N + 1) for i in range(N+1)]

dp[0][0] = 0
ans = 0
for i in range(N):
    for j in range(N, 0, -1):
        for k in range(3 * N + 1):
            if k + w[i] + minW * j <= W:
                dp[j][k+w[i]] = max((dp[j][k+w[i]], dp[j-1][k] + v[i]))
                ans = max((ans, dp[j][k+w[i]]))
# print('\n'.join(map(str, dp)))
print(ans)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Here your code !
import sys

"""
recursionlimit増やす
"""
sys.setrecursionlimit(1000000)
def knapsack(v, w, limit, n):
    """straightforward DP solution

    Arguments:
    - `v`: list of values
    - `w`: list of weights
    - `limit`: maximum limit
    - `n`: number of items
    """ 
    F = [[0] * (limit + 1) for x in range(n + 1)] 
    for i in range(0, n):                # F[-1] is all 0.
        for j in range(limit + 1):
            if j >= w[i]:
                F[i][j] = max(F[i - 1][j], F[i - 1][j - w[i]] + v[i])
            else:
                F[i][j] = F[i - 1][j]
    return F[n-1][limit]



if __name__ == '__main__':
    # ??????????????\???
    # limit = 50
    # data = [[60, 10], [100, 20], [120, 30], [210, 45], [10, 4]]
    N,W =map(int,input().split()) 
    vs=[]
    ws=[]
    for i in range(N):
        tmpv,tmpw=map(int,input().split())
        ws.append(tmpv)
        vs.append(tmpw)
    print(knapsack(vs,ws,W,N))