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:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b, c = LS()
    if a[-1] == b[0] and b[-1] == c[0]:
        print("YES")
    else:
        print("NO")
    return

#B
def B():
    a, b, c = LI()
    for i in range(1, b):
        if a * i % b == c:
            print("YES")
            return
    print("NO")
    return

#C
def C():
    _, T = LI()
    t = LI()
    ans = 0
    now = t[0]
    for i in t[1:]:
        if now + T <= i:
            ans += T
        else:
            ans += i - now
        now = i
    print(ans + T)
    return

#D
def D():
    n, W = LI()
    wv = LIR(n)
    wv.sort()
    dp = [-inf] * 30001
    dp[0] = 0
    minw =  wv[0][0]
    if minw <= 300:
        for w, v in wv:
            for i in range(30000, w - 1, -1):
                dp[i] = max(dp[i - w] + v, dp[i])
        print(max(dp[:W + 1]))
    else:
        for w, v in wv:
            w -= minw
            for i in range(n-1, -1, -1):
                for k in range(300, w - 1, -1):
                    dp[n * 300 + k] = max(dp[n * 300 + k - w] + v, dp[k])
        print(dp[:W // minw + W % minw + 1])
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b, c = LS()
    if a[-1] == b[0] and b[-1] == c[0]:
        print("YES")
    else:
        print("NO")
    return

#B
def B():
    a, b, c = LI()
    for i in range(1, b):
        if a * i % b == c:
            print("YES")
            return
    print("NO")
    return

#C
def C():
    _, T = LI()
    t = LI()
    ans = 0
    now = t[0]
    for i in t[1:]:
        if now + T <= i:
            ans += T
        else:
            ans += i - now
        now = i
    print(ans + T)
    return

#D
def D():
    n, W = LI()
    wv = LIR(n)
    wv.sort()
    dp = [-inf] * 30001
    dp[0] = 0
    minw =  wv[0][0]
    if minw <= 300:
        for w, v in wv:
            for i in range(30000, w - 1, -1):
                dp[i] = max(dp[i - w] + v, dp[i])
        print(max(dp[:W + 1]))
    else:
        for w, v in wv:
            w -= minw
            for i in range(n-1, -1, -1):
                for k in range(300, w - 1, -1):
                    dp[n * 300 + k] = max(dp[n * 300 + k - w] + v, dp[k])
        print(dp[:W // minw + W % minw])
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)

N, WW = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(N)]
W, V = zip(*l)
M = [[-1] * (WW + 1) for i in range(N + 1)]
def cal(i, w):
  if M[i][w] >= 0:
    return M[i][w]
  if i == N:
    v = 0
  elif w < W[i]:
    v = cal(i + 1, w)
  else:
    v = max(cal(i + 1, w), cal(i + 1, w - W[i]) + V[i])
  M[i][w] = v
  return v

print(cal(0, WW))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**11)

N, WW = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(N)]
W, V = zip(*l)
M = [[-1] * (WW + 1) for i in range(N + 1)]
def cal(i, w):
  if M[i][w] >= 0:
    return M[i][w]
  if i == N:
    v = 0
  elif w < W[i]:
    v = cal(i + 1, w)
  else:
    v = max(cal(i + 1, w), cal(i + 1, w - W[i]) + V[i])
  M[i][w] = v
  return v

print(cal(0, WW))

Submission status: Runtime Error

Solution code:
N, WW = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(N)]
W, V = zip(*l)
M = [[-1] * (WW + 1) for i in range(N + 1)]
def cal(i, w):
  if M[i][w] >= 0:
    return M[i][w]
  if i == N:
    v = 0
  elif w < W[i]:
    v = cal(i + 1, w)
  else:
    v = max(cal(i + 1, w), cal(i + 1, w - W[i]) + V[i])
  M[i][w] = v
  return v

print(cal(0, WW))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

N, W = map(int, input().split())
wv = [[int(i) for i in input().split()] for _ in range(N)]

wv.sort()
s, t = 0, 0
ns, nt = 0, 0
for i in range(N) :
    if s + wv[i][0] <= W :
        s += wv[i][0]
        ns += 1
    else :
        break
for i in range(N-1, -1, -1) :
    if t + wv[i][0] <= W :
        t += wv[i][0]
        nt += 1
    else :
        break
        
if ns == nt :
    wv.sort(key=lambda x: x[1], reverse=True)
    ret = 0
    for w, v in wv :
        if w < W :
            ret += v
            W -= w
    print(ret)
else :
    dp = [[0] * (W + 1) for _ in range(N + 1)]

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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

N, W = map(int, input().split())
wv = [[int(i) for i in input().split()] for _ in range(N)]

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

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

Submission status: Runtime Error

Solution code:
n, W = map(int, input().split())
w = []
v = []
for i in range(n):
    w_, v_ = map(int, input().split())
    w.append(w_)
    v.append(v_)

if sum(w) <= W:
    print(sum(v))
else:
    dp = [[0] * (W + 1) for i in range(n + 1)]  # DP テーブル

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

    print(dp[0][W])

Submission status: Runtime Error

Solution code:
n, W = map(int, input().split())
w = []
v = []
for i in range(n):
    w_, v_ = map(int, input().split())
    w.append(w_)
    v.append(v_)

dp = [[0] * (W + 1) for i in range(n + 1)]  # DP テーブル

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

print(dp[0][W])

Submission status: Runtime Error

Solution code:
#[macro_use]
mod input {

use std;
use std::io;

const SPLIT_DELIMITER: char = ' ';

#[macro_export]
#[allow(unused_macros)]
macro_rules! input {
    ( $($x:expr ),*) => {
        {
            let temp_str = input_line_str();
            let mut split_result_iter = temp_str.split_whitespace();
                $(
                let buf_split_result = split_result_iter.next();
                let buf_split_result = buf_split_result.unwrap();
                    ($x) = buf_split_result.parse().unwrap();
                )*
        }
    };
}

#[allow(dead_code)]
pub fn input_line_str() -> String {
    let mut s = String::new();
    io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

#[allow(dead_code)]
pub fn p<T>(t: T)
where
    T: std::fmt::Display,
{
    println!("{}", t);
}
}
use input::*;

use std::cmp;

fn vec_range_sum(v: &Vec<usize>, n: usize) -> usize {
    let to;
    let mut sum = 0;
    if n > v.len() {
        to = v.len();
    } else {
        to = n
    }
    for i in 0..to {
        sum += v[i];
    }
    sum
}

fn main() {
    let (n, w): (usize, usize);
    input!(n, w);
    let mut ans = 0;
    let mut vc = vec![Vec::new(); 4];
    let mut offset = 0;
    for _ in 0..n {
        let (w, v): (usize, usize);
        input!(w, v);
        if offset == 0 {
            offset = w;
        }
        vc[w - offset].push(v);
    }

    for z in &mut vc {
        z.sort();
        z.reverse();
    }

    for i in 0..w + 1 {
        if i * offset > w {
            break;
        }
        for j in 0..w + 1 {
            if i * offset + j * (offset + 1) > w {
                break;
            }
            for k in 0..w + 1 {
                if i * offset + j * (offset + 1) + k * (offset + 2) > w {
                    break;
                }
                for l in 0..w + 1 {
                    if i * offset + j * (offset + 1) + k * (offset + 2) + l * (offset + 3) > w {
                        break;
                    }
                    let mut ans_buf = 0;
                    ans_buf += vec_range_sum(&vc[0], i);
                    ans_buf += vec_range_sum(&vc[1], j);
                    ans_buf += vec_range_sum(&vc[2], k);
                    ans_buf += vec_range_sum(&vc[3], l);
                    ans = cmp::max(ans_buf, ans);
                }
            }
        }
    }
    p(ans);
}

Submission status: Runtime Error

Solution code:


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()

Submission status: Runtime Error

Solution code:


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())

Submission status: Runtime Error

Solution code:
N,W = map(int,input().split())
wv = list(list(map(int,input().split()))for i in range(N))
dp = [[0]*(W+1) for i in range(N+1)]

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

Submission status: Runtime Error

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

# import numpy as np
# from scipy.special import perm
# from scipy.special import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

########
class Edge:
    def __init__(self, from_edge, to_edge, cost):
        self.from_edge = from_edge
        self.to_edge = to_edge
        self.cost = cost

def bellman_ford(start, edges, node_num):
    dist = [INF] * node_num
    dist[start] = 0
    flag = False
    for i in range(node_num):
        for edge in edges:
            if dist[edge.to_edge] > dist[edge.from_edge] + edge.cost:
                dist[edge.to_edge] = dist[edge.from_edge] + edge.cost
                if i == N-1 and edge.to_edge == (node_num - 1):
                    flag = True
    return dist, flag


N, M = l_inpl()
edges = []

for _ in range(M):
    ai, bi, ci = l_inpl()
    edges.append(Edge(ai-1, bi-1, -ci))

dist, flag = bellman_ford(0, edges, N)
# print(dist)
if flag:
    print("inf")
else:
    print(-dist[N-1])

Submission status: Runtime Error

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

dp = [[0]*(W+1) for _ in range(N+1)] #dp[i][j]...i番目以降の品物から重さの総和がj以下となるように選んだ時の価値の総和の最大値

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

print(dp[0][W])

Submission status: Runtime Error

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right

# import numpy as np
# from scipy.special import perm
# from scipy.special import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

########

N, W = l_inpl()
w, v = [], []

for _ in range(N):
    wi, vi = l_inpl()
    w.append(wi)
    v.append(vi)

# dp[i][sum_w]: i-1番目までの品物から重さがWを超えないように選んだときの価値の総和の最大値
dp = [[0] * (W+1) for _ in range(N+1)]
# print(dp)
dp[0][W] = 0

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

print(dp[N][W])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline


def main():
    print(search_with_memo(0, W))


def search_with_memo(i, rest):
    if memo[i][rest] != None:
        return memo[i][rest]

    if i == N:
        return 0
    elif rest < items[i].w:
        through = search_with_memo(i + 1, rest)
        memo[i+1][rest] = through
        return through
    else:
        selected = search_with_memo(i+1, rest - items[i].w) + items[i].v
        memo[i+1][rest - items[i].w] = selected
        through = search_with_memo(i+1, rest)
        memo[i+1][rest] = through
        return max(selected, through)


def all_search(i, rest):
    if i == N:
        return 0
    elif rest < items[i].w:
        return all_search(i+1, rest)
    else:
        selected = all_search(i+1, rest - items[i].w) + items[i].v
        through = all_search(i+1, rest)
        return max(selected, through)


class Item():

    def __init__(self, v, w):
        self.v = v
        self.w = w


if __name__ == "__main__":
    N, W = [int(ele) for ele in input().split()]
    items = [None] * N
    memo = [[None] * (W*2) for _ in range(N*2)]
    for idx in range(N):
        w, v = [int(ele) for ele in input().split()]
        items[idx] = Item(v, w)

    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline


def main():
    #print(all_search(0, W))
    print(search_with_memo(0, W))


def search_with_memo(i, rest):
    if memo[i][rest] != None:
        return memo[i][rest]

    if i == N:
        return 0
    elif rest < items[i].w:
        through = search_with_memo(i+1, rest)  # through
        memo[i+1][rest] = through
        return through
    else:
        selected = search_with_memo(i+1, rest - items[i].w) + items[i].v
        memo[i+1][rest - items[i].w] = selected
        through = search_with_memo(i+1, rest)
        memo[i+1][rest] = through
        return max(selected, through)


def all_search(i, rest):
    if i == N:
        return 0
    elif rest < items[i].w:
        return all_search(i+1, rest)
    else:
        selected = all_search(i+1, rest - items[i].w) + items[i].v
        through = all_search(i+1, rest)
        return max(selected, through)


class Item():

    def __init__(self, v, w):
        self.v = v
        self.w = w


if __name__ == "__main__":
    N, W = [int(ele) for ele in input().split()]
    items = [None] * N
    memo = [[None] * (W+1) for _ in range(N+1)]
    for idx in range(N):
        w, v = [int(ele) for ele in input().split()]
        items[idx] = Item(v, w)

    main()

Submission status: Runtime Error

Solution code:
from numpy import*
N,W=map(int, input().split())
dp=zeros(W+1)
for i in range(N):
    w,v=map(int, input().split())
    dp[w:]=maximum(dp[w:], dp[:-w]+v)
print(int(max(dp)))

Submission status: Runtime Error

Solution code:
N,W=map(int,input().split())
2.dp=[0]*(W+1)
3.for i in range(N):
4.    w,v=map(int,input().split())
5.    for p,q in enumerate(dp):
6.        if p+w<=W:
7.            dp[p+w]=max(dp[p+w],q+v)
8.print(max(dp))

Submission status: Runtime Error

Solution code:
N,W=map(int,input().split())
dp=[0]*(W+1)
for i in range(N):
    w,v=map(int,input().split())
    for p,q in enumerate(dp.copy()):
        if p+w<=W:
            dp[p+w]=max(dp[p+w],q+v)
print(max(dp))

Submission status: Runtime Error

Solution code:
from collections import defaultdict as d
s=d(int)
s[0]=0
n,w=map(int,input().split())
for i in range(n):
    q,v=map(int,input().split())
    c=s.copy()
    for p,r in c.items():
        if p+q<=w:
            s[p+q]=max(c[p+q],c[p]+v)
print(max(s.values()))

Submission status: Runtime Error

Solution code:
def simple_knapsack(N: int, W: int, items: list) -> int:
    # dp[n][w] は n~N 番目の品物を利用して重さが w 以下となるときの
    # 最大価値
    dp = [[0] * (W+1) for _ in range(N+1)]

    for i, (iw, iv) in enumerate(items):
        for w in range(W+1):
            if w < iw:
                dp[N-i-1][w] = dp[N-i][w]
            else:
                dp[N-i-1][w] = max(dp[N-i][w], dp[N-i][w-iw]+iv)
    return dp[0][W]


if __name__ == "__main__":
    N = 0
    N, W = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(N)]
    ans = simple_knapsack(N, W, items)
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

def main():
    N,W = map(int,input().split())
    info = []
    for i in range(N):
        w,v = map(int,input().split())
        if i == 0:
            w1 = w
        w = w - (w1-1)
        info.append((w,v))
    # dp[i][j][k]
    # dp[i][j][k] = max(dp[i-1][j][k],dp[i-1][j-w][k-1])
    # dp[0][j][0] = 0
    # ans = max(dp[N][j][k] w1*k + j <= W)
    dp = [[[0]*(N+1) for _ in range(400)] for _ in range(N+1)]
    for i in range(1,N+1):
        w = info[i-1][0]; v = info[i-1][1]
        for j in range(400):
            for k in range(1,N+1):
                dp[i][j][k] = dp[i-1][j][k]
                if j - w >= 0:
                    if dp[i][j][k] < dp[i-1][j-w][k-1] + v:
                        dp[i][j][k] = dp[i-1][j-w][k-1] + v

    ans = -1
    for k in range(N+1):
        for j in range(W-(w1-1)*k + 1):
            if dp[N][j][k] > ans:
                ans = dp[N][j][k]
    print(ans)

main()

Submission status: Runtime Error

Solution code:
N,W = map(int, input().split())
weight=[]
values=[]
for idx in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    values.append(v)
dp=[[0]*(W+1) for i in range(N+1)]

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

print(dp[N][W])

Submission status: Runtime Error

Solution code:
a,b,c = input().split()
if a[-1]==b[0] and b[-1]==c[0]:
  print("YES")
else:
  print("NO")

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(N)]
dp = [[0] * (W+1) for i in range(N+1)]

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


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

Submission status: Runtime Error

Solution code:
n,w=map(int,input().split())
d={}
p=0
ans=[0,0]
u=[[] for i in range(4)]
for i in range(n):
    a,b=map(int,input().split())
    if a in d: d[a].append(b)
    else:d[a]=[0,b]
    p=max(p,a)
for i in range(4):
    if p-i in d: d[p-i].sort()
    else: d[p-i]=[0]

for x in range(4):
    if len(d[p-x])*(p-x)+ans[0]<=w:
        ans[0]+=len(d[p-x])*(p-x)
        ans[1]+=sum(d[p-x])
        u[x]=[o for o in d[p-x]]
        d[p-x]=[0]
    else:
        for i in range(-1,-1-len(d[p-x]),-1):
            if p+ans[0]-x<=w:
                ans[0]+=p-x
                ans[1]+=d[p-x][-1]
                u[x].append(d[p-x].pop())
            else:
                break
#u[-1].sort(reverse=True)
while len(u[0]):
    if u[0][-1]<d[p-1][-1]:
        ans[0]-=1
        ans[1]+=d[p-1][-1]
        u[-1].pop()
        u[-1].append(d[p-1].pop())
    else:
        break
print(ans[1])

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
w = []
v = []
for i in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)
w_adjust = []
for i in range(N):
    w_adjust.append(w[i]-w[0])

a = w[0]
dp = [[[0 for i in range(N+1)] for j in range(N*3+10)] for k in range(N+1)]
#i個目までの物のうちk個選んで重さの和がjになる中での最大価値
for i in range(N):
    for j in range(3*N):
        for k in range(N):
            if j + w_adjust[i] > W - a*(k+1):
                dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
            else:
                dp[i+1][j+w_adjust[i]][k+1] = max(dp[i+1][j+w_adjust[i]][k+1], dp[i][j][k] + v[i])
                dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
ans = [0]
for i in range(N+1):
    if W - a*i >= 0:
        ans.append(dp[N][W-a*i][i])

print(max(ans))

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
w = []
v = []
for i in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)
w_adjust = []
for i in range(N):
    w_adjust.append(w[i]-w[0])

a = w[0]
dp = [[[0 for i in range(N+1)] for j in range(N*3+10)] for k in range(N+1)]
#i個目までの物のうちk個選んで重さの和がjになる中での最大価値
for i in range(N):
    for j in range(3*N):
        for k in range(N):
            dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
            dp[i+1][j+w_adjust[i]][k+1] = max(dp[i+1][j+w_adjust[i]][k+1], dp[i][j][k] + v[i])

ans = []
for i in range(N+1):
    if W - a*i >= 0 and W - a*i <= N*3 + 5
        ans.append(dp[N][W-a*i][i])
    else:
        ans.append(0)
print(max(ans))

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
w = []
v = []
for i in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)
w_adjust = []
for i in range(N):
    w_adjust.append(w[i]-w[0])

a = w[0]
dp = [[[0 for i in range(N+1)] for j in range(N*3+10)] for k in range(N+1)]
#i個目までの物のうちk個選んで重さの和がjになる中での最大価値
for i in range(N):
    for j in range(3*N):
        for k in range(N):
            dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
            dp[i+1][j+w_adjust[i]][k+1] = max(dp[i+1][j+w_adjust[i]][k+1], dp[i][j][k] + v[i])

ans = []
for i in range(N+1):
    if W - a*i >= 0:
        ans.append(dp[N][W-a*i][i])
    else:
        ans.append(0)
print(max(ans))

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
w = []
v = []
for i in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)
w_adjust = []
for i in range(N):
    w_adjust.append(w[i]-w[0])

a = w[0]
dp = [[[0 for i in range(N+1)] for j in range(N*3+4)] for k in range(N+1)]
#i個目までの物のうちk個選んで重さの和がjになる中での最大価値
for i in range(N):
    for j in range(3*N):
        for k in range(N):
            dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
            dp[i+1][j+w_adjust[i]][k+1] = max(dp[i+1][j+w_adjust[i]][k+1], dp[i][j][k] + v[i])

ans = []
for i in range(N+1):
    if W - a*i >= 0:
        ans.append(dp[N][W-a*i][i])
    else:
        ans.append(0)
print(max(ans))

Submission status: Runtime Error

Solution code:
N, W = map( int, input().split())
dp = [0]*(W+1)
for _ in range(N):
    w, v = map( int, input().split())
    for i in range(W,-1,-1):
        if i >= w:
            dp[i] = max( dp[i], dp[i-w]+v)
        else:
            continue
print(dp[-1])