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: Wrong Answer

Solution code:
import sys
from collections import deque
import copy

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, W] =  [long(input_raw[0]), long(input_raw[1])]
    v = []
    item = {}
    v_sum = {}
    for i in range(N):
        input_raw = read_func().strip().split()
        [wi, vi] =  [long(input_raw[0]), long(input_raw[1])]
        if wi not in item:
            item[wi] = [vi]
        else:
            item[wi].append(vi)

    for i in range(4 - len(item)):
        item[-(i + 1)] = [0]

    w_list = []
    for wi in item:
        item[wi].sort(reverse = True)
        w_list.append(wi)
        v_sum[wi] = [0 for i in range(len(item[wi]) + 1)]
        v_sum[wi][1] = item[wi][0]
        for i in range(1, len(item[wi])):
            v_sum[wi][i + 1] = v_sum[wi][i] + item[wi][i]

    max_value = 0
    for i in range(len(item[w_list[0]]) + 1):
        for j in range(len(item[w_list[1]]) + 1):
            for k in range(len(item[w_list[2]]) + 1):
                for l in range(len(item[w_list[3]]) + 1):
                    if W - (i * max(0, w_list[0]) + j * max(0, w_list[1]) + k * max(0, w_list[2]) + l * max(0, w_list[3])) >= 0:
                        value = v_sum[w_list[0]][i] + v_sum[w_list[1]][j] + v_sum[w_list[2]][k] + v_sum[w_list[3]][k]
                        if max_value < value:
                            max_value = value
    print max_value

##    W_ = long(N * 4 + 1)
##    dp = [[0L for j in range((W_) + 1)] for i in range(N + 1)]
##
##    for i in range(N):
##        for j in range(W_ + 1):
##
##            k = ((j - 1)%4 +  ((j - 1)/4 +1) * w[0]) - w[i]
##            #print k, j, w[i]
##            if k  < 0 or j == 0:
##                dp[i + 1][j] = dp[i][j]
##            else:
##                if k >= w[0]:
##                    l = k / w[0] + 3 * (k / w[0] - 1)
##                else:
##                    l = 0
##                print i ,w[i], k, l
##                dp[i + 1][j] = max(dp[i][j], dp[i][l] + v[i])
##
##    maximum = 0
##    for i in range(1, W_ + 1):
##        if maximum < dp[N][i] and (i - 1)%4 +  ((i - 1)/4 +1) * w[0] <= W:
##            maximum = dp[N][i]
##
##    print maximum


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
import copy

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, W] =  [long(input_raw[0]), long(input_raw[1])]
    v = []
    w = []
    for i in range(N):
        input_raw = read_func().strip().split()
        [wi, vi] =  [long(input_raw[0]), long(input_raw[1])]
        v.append(vi)
        w.append(wi)

    W_ = long(N * 4)
    dp = [[0L for j in range((W_) + 1)] for i in range(N + 1)]

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

    if W - w[0] + 1 <= N * 4:
        print dp[N][max(0, W - w[0] + 1)]
    else:
        print dp[N][N * 4]


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
import copy

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, W] =  [long(input_raw[0]), long(input_raw[1])]
    v = []
    w = []
    for i in range(N):
        input_raw = read_func().strip().split()
        [wi, vi] =  [long(input_raw[0]), long(input_raw[1])]
        v.append(vi)
        w.append(wi)

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

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

    if W - w[0] + 1 <= N * 3:
        print dp[N][max(0, W - w[0] + 1)]
    else:
        print dp[N][N * 3]


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
import copy

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, W] =  [int(input_raw[0]), int(input_raw[1])]
    v = []
    w = []
    for i in range(N):
        input_raw = read_func().strip().split()
        [wi, vi] =  [int(input_raw[0]), int(input_raw[1])]
        v.append(vi)
        w.append(wi)

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

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

    if W - w[0] + 1 <= N * 3:
        print dp[N][max(0, W - w[0] + 1)]
    else:
        print dp[N][N * 3]


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
import copy

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, W] =  [int(input_raw[0]), int(input_raw[1])]
    v = []
    w = []
    for i in range(N):
        input_raw = read_func().strip().split()
        [wi, vi] =  [int(input_raw[0]), int(input_raw[1])]
        v.append(vi)
        w.append(wi)

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

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

    if W - w[0] <= N * 3:
        print dp[N][max(0, W - w[0])]
    else:
        print dp[N][N * 3]


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
import copy

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, W] =  [int(input_raw[0]), int(input_raw[1])]
    v = []
    w = []
    for i in range(N):
        input_raw = read_func().strip().split()
        [wi, vi] =  [int(input_raw[0]), int(input_raw[1])]
        v.append(vi)
        w.append(wi)

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

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

    if W - w[0] <= N * 3:
        print dp[N][max(0, W - w[0])]
    else:
        print dp[N][N * 3]


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,W=map(int,input().split())
table=[[] for i in range(4)]
a,b = map(int,input().split())
table[0].append(b)
for i in range(1,N):
    w,v = map(int,input().split())
    table[w-a].append(v)
for i in range(4):
    table[i].sort()
    table[i]+=[0]
ans=0
for i in range(len(table[3])+1):
    for j in range(len(table[1])+1):
        for k in range(len(table[2])+1):
            t=(W-a*(i+j+k)-j-2*k-3*i)//a
            if t<0:
                flag =True
                break
            else:
                x=sum(table[3][-i-1:]+table[1][-j-1:]+table[2][-k-1:]+table[0][t-1:])
                ans=max(ans,x)  
print(ans)

Submission status: Wrong Answer

Solution code:
ints = input().split(" ")
N = int(ints[0])
maxW = int(ints[1])
ints = input().split(" ")
a = int(ints[0])
b = int(ints[1])
weight = [a, a+1, a+2, a+3] 
va = [[0,b],[0],[0],[0]]
for i in range(1, N):
	ins = input().split(" ")
	w = int(ins[0])
	v = int(ins[1])
	for j in range(0, 4):
		if w == weight[j]:
			va[j].append(v)
va.sort()
sum = [[0],[0],[0],[0]]
for j in range(0, 4):
	for i in range(1, len(va[j])):
		try:
			sum[j].append(sum[j][i-1] + va[j][i])
		except:
			pass
ans = 0
for i in range(0, len(va[0])):
	for j in range(0, len(va[1])):
		for k in range(0, len(va[2])):
			for l in range(0, len(va[3])):
				sumw = weight[0]*i + weight[1]*j +weight[2]*k + weight[3]*l
				if(sumw <= maxW):
					ans = max(sum[0][i]+sum[1][j]+sum[2][k]+sum[3][l],ans)
print(ans)

Submission status: Wrong Answer

Solution code:
ints = input().split(" ")
N = int(ints[0])
maxW = int(ints[1])
ints = input().split(" ")
a = int(ints[0])
b = int(ints[1])
weight = [a, a+1, a+2, a+3] 
va = [[0,b],[0],[0],[0]]
for i in range(1, N):
	ins = input().split(" ")
	w = int(ins[0])
	v = int(ins[1])
	for j in range(0, 4):
		if w == weight[j]:
			va[j].append(v)
sum = [[0],[0],[0],[0]]
for j in range(0, 4):
	for i in range(1, len(va[j])):
		try:
			sum[j].append(sum[j][i-1] + va[j][i])
		except:
			pass
ans = 0
for i in range(0, len(va[0])):
	for j in range(0, len(va[1])):
		for k in range(0, len(va[2])):
			for l in range(0, len(va[3])):
				sumw = weight[0]*i + weight[1]*j +weight[2]*k + weight[3]*l
				if(sumw <= maxW):
					ans = max(sum[0][i]+sum[1][j]+sum[2][k]+sum[3][l],ans)
print(ans)

Submission status: Wrong Answer

Solution code:
while True:
	try:
		ins = input().split(" ")
		N = int(ins[0])
		Wmax = int(ins[1])
		A = [[0,0]]
		B = [[0,0]]
		C = [[0,0]]
		D = [[0,0]]
		thing = input().split(" ")
		A.append([int(thing[0]), int(thing[1])])
		for i in range(1, N):
			thing = input().split(" ")
			w = int(thing[0])
			v = int(thing[1])
			if w == A[1][0]:
				A.append([w,v])
			elif w == A[1][0] + 1:
				B.append([w,v])
			elif w == A[1][0] + 2:
				C.append([w,v])
			else:
				D.append([w,v])


		A.sort(key = lambda x: x[1])
		B.sort(key = lambda x: x[1])
		C.sort(key = lambda x: x[1])
		D.sort(key = lambda x: x[1])

		sumA = [[0,0]]
		sumB = [[0,0]]
		sumC = [[0,0]]
		sumD = [[0,0]]

		for i in range(1, len(A)):
			sumA.append([ sumA[i-1][0]+A[i][0], sumA[i-1][1]+A[i][1] ] )

		for i in range(1, len(B)):
			sumB.append([ sumB[i-1][0]+B[i][0], sumB[i-1][1]+B[i][1] ] )

		for i in range(1, len(C)):
			sumC.append([ sumC[i-1][0]+C[i][0], sumC[i-1][1]+C[i][1] ] )

		for i in range(1, len(D)):
			sumD.append([ sumD[i-1][0]+D[i][0], sumD[i-1][1]+D[i][1] ] )
		 
		ans = 0;  
		for i in range(0, len(A)):  
		    for j in range(0, len(B)):
		       	for k in range(0, len(C)):   
		            for l in range(0, len(D)):
		                sumw = sumA[i][0] + sumB[j][0] + sumC[k][0] + sumD[l][0]  
		                if sumw <= Wmax: 
		                    ans = max(ans,sumA[i][1]+sumB[j][1]+sumC[k][1]+sumD[l][1])  
		print(ans)
	except:
		break

Submission status: Wrong Answer

Solution code:
ins = input().split(" ")
N = int(ins[0])
Wmax = int(ins[1])
A = [[0,0]]
B = [[0,0]]
C = [[0,0]]
D = [[0,0]]
thing = input().split(" ")
A.append([int(thing[0]), int(thing[1])])
for i in range(1, N):
	thing = input().split(" ")
	w = int(thing[0])
	v = int(thing[1])
	if w == A[1][0]:
		A.append([w,v])
	elif w == A[1][0] + 1:
		B.append([w,v])
	elif w == A[1][0] + 2:
		C.append([w,v])
	else:
		D.append([w,v])


A.sort(key = lambda x: x[1])
B.sort(key = lambda x: x[1])
C.sort(key = lambda x: x[1])
D.sort(key = lambda x: x[1])

sumA = [[0,0]]
sumB = [[0,0]]
sumC = [[0,0]]
sumD = [[0,0]]

for i in range(1, len(A)):
	sumA.append([ sumA[i-1][0]+A[i][0], sumA[i-1][1]+A[i][1] ] )

for i in range(1, len(B)):
	sumB.append([ sumB[i-1][0]+B[i][0], sumB[i-1][1]+B[i][1] ] )

for i in range(1, len(C)):
	sumC.append([ sumC[i-1][0]+C[i][0], sumC[i-1][1]+C[i][1] ] )

for i in range(1, len(D)):
	sumD.append([ sumD[i-1][0]+D[i][0], sumD[i-1][1]+D[i][1] ] )

sumv = 0;  
ans = 0;  
for i in range(0, len(A)):  
    for j in range(0, len(B)):
       	for k in range(0, len(C)):   
            for l in range(0, len(D)):
                sumw = sumA[i][0] + sumB[j][0] + sumC[k][0] + sumD[l][0]  
                if sumw <= Wmax: 
                    ans = max(ans,sumA[i][1]+sumB[j][1]+sumC[k][1]+sumD[l][1])  
print(ans)

Submission status: Wrong Answer

Solution code:
N, W = list(map(int, input().split()))

values = [[] for i in range(4)]

w0, v0 = list(map(int, input().split()))
values[0].append(v0)

for i in range(N-1):
    w, v = list(map(int, input().split()))
    values[w-w0].append(v)

for i in range(4):
    values[i].sort()
    for j in range(len(values[i])-1):
        values[i][j+1] = values[i][j] + values[i][j+1]
    values[i].append(0)

res = 0

for i1 in range(len(values[0])+1):
    for i2 in range(len(values[1])+1):
        for i3 in range(len(values[2])+1):
            for i4 in range(len(values[3])+1):
                if(w0*i1 + (w0+1)*i2 + (w0+2)*i3 + (w0+3)*i4 <= W):
                    res = max(res, values[0][i1-1] + values[1][i2-1] + values[2][i3-1] + values[3][i4-1])

print(res)

Submission status: Wrong Answer

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

N, W = map(int, input().split())

ws = []
vs = []

for i in range(N):
    w, v = map(int, input().split())
    ws.append(w)
    vs.append(v)

dp = [{} for i in range(N)]
dp[0][ws[0]] = vs[0]
dp[0][0] = 0

for i in range(1,N):
    tmp = dp[i-1].copy()
    for key, value in tmp.items():
        dp[i].setdefault(ws[i]+key, 0)
        #print(i, key, value, value+vs[i], dp[i][ws[i]+key])
        dp[i][ws[i]+key] = max(value+vs[i], dp[i][ws[i]+key])
        dp[i][key] = value

max_value = 0
for i in range(N):
    tmp = []
    for key, value in dp[i].items():
        if key <= W:
            tmp.append(value)
    if len(tmp)!=0:
        max_value = max(max_value, max(tmp))

#print(dp)
print(max_value)

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())  # N<=100, W<=10**9
w, v = [0] * N, [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())  # すべての i=2,3,…,N について、w1 ≦ wi ≦ w1+3

#

def kaihou():
    monos_by_omosa = [[] for _ in range(4)]
    w0 = w[0]
    for i in range(N):
        monos_by_omosa[w[i] - w0].append(v[i])
    for i in range(4):
        monos_by_omosa[i].sort
        monos_by_omosa[i].reverse
    # print(monos_by_omosa)
    ans = 0
    for i in range(N + 1):
        if i > len(monos_by_omosa[0]):
            break
        w0i = (w0) * i
        if w0i > W:
            break

        for j in range(N + 1 - i):
            if j > len(monos_by_omosa[1]):
                break
            w1j = (w0 + 1) * j
            if w0i + w1j > W:
                break

            for k in range(N + 1 - i - j):
                if k > len(monos_by_omosa[2]):
                    break
                w2k  = (w0 + 2) * k
                if w0i + w1j + w2k > W:
                    break

                for l in range(N + 1 - i - j - k):
                    if l > len(monos_by_omosa[3]):
                        break
                    w3l = (w0 + 3) * l
                    if w0i + w1j + w2k + w3l > W:
                        break

                    val = sum(monos_by_omosa[0][:i])
                    val += sum(monos_by_omosa[1][:j])
                    val += sum(monos_by_omosa[2][:k])
                    val += sum(monos_by_omosa[3][:l])
                    ans = max(ans, val)
    return ans

print(kaihou())

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())

items = [tuple(map(int,input().split())) for i in range(N)]

from collections import defaultdict
dp = defaultdict(int) # w -> v
dp[0] = 0

for w,v in items:
  for tw,tv in list(dp.items()):
    if tw+w <= W:
      dp[tw+w] = max(tv+v, dp[tw+w])

print(max(dp.items())[1])

Submission status: Wrong Answer

Solution code:
a = list(map(int, input().split()))
N,W = a[0],a[1]
tup =zip(a[2::2], a[3::2])
dic = {}
for val in tup:
    if val[0] in dic.keys():
        if val[1] >= dic[val[1]]:
            dic.update({val[0]:val[1]})
    else:
        dic.update({val[0]:val[1]})
v = 0
i= 0
for i in range(len(dic.keys())):
    for element in itertools.combinations(dic.keys(),i):
        if sum(element)<= W:
            sm = sum(map(lambda x: dic[x], element))
            i = max(i,sm)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
from itertools import izip


def sol(n, w, wis, vis):
    rv = 0
    best = dd(lambda: (0, n))
    for i, (wi, vi) in enumerate(izip(wis, vis)):
        if wi <= w:
            cv, ci = best[wi]
            if cv < vi or cv == vi and ci > i:
                best[wi] = (vi, i)
            rv = max(vi, rv)

    frontline = [(i, wis[i], vis[i]) for i in xrange(n - 1, -1, -1)]
    while frontline:
        last, cw, cv = frontline.pop()
        for i in xrange(last + 1, n):
            nw, nv = cw + wis[i], cv + vis[i]
            bv, bi = best[nw]
            if nw <= w and (bv < nv or bv == nv and bi > i):
                best[nw] = (nv, i)
                frontline.append((i, nw, nv))
                rv = max(rv, nv)

    return rv


if __name__ == "__main__":
    n, w = map(int, raw_input().strip().split())
    wis, vis = [], []
    for _ in xrange(n):
        wi, vi = map(int, raw_input().strip().split())
        wis.append(wi)
        vis.append(vi)
    print sol(n, w, wis, vis)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
from itertools import izip


def sol(n, w, wis, vis):
    rv = 0
    best = dd(int)
    for wi, vi in izip(wis, vis):
        if wi < w:
            best[wi] = max(best[wi], vi)
            rv = max(vi, rv)

    frontline = [(i, wis[i], vis[i]) for i in xrange(n - 1, -1, -1)]
    while frontline:
        last, cw, cv = frontline.pop()
        for i in xrange(last + 1, n):
            nw, nv = cw + wis[i], cv + vis[i]
            if nw <= w and best[nw] < nv:
                best[nw] = nv
                frontline.append((i, nw, nv))
                rv = max(rv, nv)

    return rv


if __name__ == "__main__":
    n, w = map(int, raw_input().strip().split())
    wis, vis = [], []
    for _ in xrange(n):
        wi, vi = map(int, raw_input().strip().split())
        wis.append(wi)
        vis.append(vi)
    print sol(n, w, wis, vis)

Submission status: Wrong Answer

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

sorted_item_list = sorted(item_list,key=lambda item:float(item[1])/float(item[0]),reverse=True)

w_sum = 0
v_sum = 0
count = 0
max_v_sum = 0
for s in range(N):
    w_sum = 0
    v_sum = 0
    count = 0
    for i in range(N):
        while w_sum<=W and count+i+s<N:
            w_sum+=sorted_item_list[count+i+s][0]
            v_sum+=sorted_item_list[count+i+s][1]
            count+=1
        if w_sum>W:
            w_sum-=sorted_item_list[count+i+s-1][0]
            v_sum-=sorted_item_list[count+i+s-1][1]
    if max_v_sum<v_sum:
        max_v_sum=v_sum

print str(max_v_sum)

Submission status: Wrong Answer

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

sorted_item_list = sorted(item_list,key=lambda item:float(item[1])/float(item[0]),reverse=True)

w_sum = 0
v_sum = 0
count = 0
for i in range(N):
    while w_sum<=W and count+i<N:
        w_sum+=sorted_item_list[count+i][0]
        v_sum+=sorted_item_list[count+i][1]
        count+=1
    if w_sum>W:
        w_sum-=sorted_item_list[count+i-1][0]
        v_sum-=sorted_item_list[count+i-1][1]

print str(v_sum)

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
v = [[] for i in range(4)]  # w1+x
w1 = -1

for i in range(N):
    a, b = map(int, input().split())
    if i == 0:
        w1 = a
    v[a - w1].append(b)

for i in range(4):
    v[i].reverse()  # 価値の高い順にソート

ret = 0

for i in range(len(v[0]) + 1):
    for j in range(len(v[1]) + 1):
        for k in range(len(v[2]) + 1):
            for l in range(len(v[3]) + 1):
                w = (i + j + k + l) * w1 + (i * 0 + j * 1 + k * 2 + l * 3)
                sum_v = sum(v[0][:i]) + sum(v[1][:j]) + sum(v[2][:k]) + sum(v[3][:l])
                if w <= W:
                    ret = max(ret, sum_v)
print(ret)

Submission status: Wrong Answer

Solution code:

import bisect

if 1:
    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_)
else:
    N,W = 4,6
    w = [2,3,4,3]
    v = [1,4,10,4]

w0 = w[0]

idxs = set()
for i in range(N+1):
    for j in range(3*i+1):
        if i*w0+j <= W:
            idxs.add(i*w0+j)
idxs = sorted(list(idxs))
idx_dict = {idx:i for i,idx in enumerate(idxs)}

dp = [[0 for j in range(len(idxs))] for i in range(N+1)]

for i in range(N):
    for j in range(len(idxs)):
        if idxs[j] < w[i]:
            dp[i+1][j] = dp[i][j]
        else:
            if 1:
                k = bisect.bisect_left(idxs, idxs[j]-w[i])
                try:
                    dp[i+1][j] = max([dp[i][j],dp[i][idx_dict[idxs[k]]]+v[i]])
                except:
                    dp[i+1][j] = dp[i][j]
            else:
                try:
                    dp[i+1][j] = max([dp[i][j],dp[i][idx_dict[idxs[j]-w[i]]]+v[i]])
                except:
                    dp[i+1][j] = dp[i][j]
                
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:

import bisect

if 1:
    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_)
else:
    N,W = 4,6
    w = [2,3,4,3]
    v = [1,4,10,4]

w0 = w[0]

idxs = set()
for i in range(N+1):
    for j in range(3*i+1):
        if i*w0+j <= W:
            idxs.add(i*w0+j)
idxs = sorted(list(idxs))
idx_dict = {idx:i for i,idx in enumerate(idxs)}

dp = [[0 for j in range(len(idxs))] for i in range(N+1)]

for i in range(N):
    for j in range(len(idxs)):
        if idxs[j] < w[i]:
            dp[i+1][j] = dp[i][j]
        else:
            if 0:
                k = bisect.bisect_left(idxs, idxs[j]-w[i])
                try:
                    dp[i+1][j] = max([dp[i][j],dp[i][idx_dict[idxs[k]]]+v[i]])
                except:
                    dp[i+1][j] = dp[i][j]
            else:
                try:
                    dp[i+1][j] = max([dp[i][j],dp[i][idx_dict[idxs[j]-w[i]]]+v[i]])
                except:
                    dp[i+1][j] = dp[i][j]
                
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
import bisect

if 1:
    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_)
else:
    N,W = 4,6
    w = [2,3,4,3]
    v = [1,4,10,4]

w0 = w[0]

idxs = set()
for i in range(N+1):
    for j in range(3*i+1):
        if i*w0+j <= W:
            idxs.add(i*w0+j)
idxs = list(idxs) 
idx_dict = {idx:i for i,idx in enumerate(idxs)}

dp = [[0 for j in range(len(idxs))] for i in range(N+1)]

for i in range(N):
    for j in range(len(idxs)):
        if idxs[j] < w[i]:
            dp[i+1][j] = dp[i][j]
        else:
            if 0:
                k = bisect.bisect_left(idxs, idxs[j]-w[i])
                try:
                    dp[i+1][j] = max([dp[i][j],dp[i][idx_dict[idxs[k]]]+v[i]])
                except:
                    dp[i+1][j] = dp[i][j]
            else:
                try:
                    dp[i+1][j] = max([dp[i][j],dp[i][idx_dict[idxs[j]-w[i]]]+v[i]])
                except:
                    dp[i+1][j] = dp[i][j]
                
print(dp[-1][-1]%1000000009)

Submission status: Wrong Answer

Solution code:
import bisect

if 1:
    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_)
else:
    N,W = 4,6
    w = [2,3,4,3]
    v = [1,4,10,4]

w0 = w[0]

idxs = set()
for i in range(N+1):
    for j in range(3*i+1):
        if i*w0+j <= W:
            idxs.add(i*w0+j)
idxs = list(idxs) 
idx_dict = {idx:i for i,idx in enumerate(idxs)}

dp = [[0 for j in range(len(idxs))] for i in range(N+1)]

for i in range(N):
    for j in range(len(idxs)):
        if idxs[j] < w[i]:
            dp[i+1][j] = dp[i][j]
        else:
            if 1:
                k = bisect.bisect_left(idxs, idxs[j]-w[i])
                try:
                    dp[i+1][j] = max([dp[i][j],dp[i][idx_dict[idxs[k]]]+v[i]])
                except:
                    dp[i+1][j] = dp[i][j]
            else:
                try:
                    dp[i+1][j] = max([dp[i][j],dp[i][idx_dict[idxs[j]-w[i]]]+v[i]])
                except:
                    dp[i+1][j] = dp[i][j]
                
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
import sys
import random

def rd():
        return sys.stdin.readline().rstrip()

def rdi():
        return [ long(x) for x in rd().split() ]

m = {}
def update(W, wi, vi):
        if wi > W:
                return
        global m
        ks = m.keys()
        a = set()
        for wj in ks:
                wk = wj + wi
                if wk <= W:
                        vk = m[wj] + vi
                        if wk not in m or m[wk] < vk:
                                m[wk] = vk
                                a.add(wk)
        if wi not in m or m[wi] < vi:
                m[wi] = vi
                a.add(wi)
        b = m.keys()
        for wj in a:
                if wj not in m:
                        continue
                for wk in b:
                        if wj in m and wk in m and wk > wj and m[wk] <= m[wj]:
                                del(m[wk])

def calc(W, w, v):
        global m
        m = {}
        for i in range(len(w)):
                update(W, w[i], v[i])
        print max(m.values() + [0])

N, W = rdi()
w = []
v = []
for i in range(N):
        wi, vi = rdi()
        w.append(wi)
        v.append(vi)
calc(W, w, v)

Submission status: Wrong Answer

Solution code:

import bisect

if 1:
    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_)
else:
    N,W = 4,6
    w = [2,3,4,3]
    v = [1,4,10,4]

w0 = w[0]

idxs = set()
for i in range(N+1):
    for j in range(3*i+1):
        if i*w0+j <= W:
            idxs.add(i*w0+j)
idxs = list(idxs) 
idx_dict = {idx:i for i,idx in enumerate(idxs)}

dp = [[0 for j in range(len(idxs))] for i in range(N+1)]

for i in range(N):
    for j in range(len(idxs)):
        if idxs[j] < w[i]:
            dp[i+1][j] = dp[i][j]
        else:
            if 0:
                k = bisect.bisect_left(idxs, idxs[j]-w[i])
                dp[i+1][j] = max([dp[i][j],dp[i][idx_dict[idxs[k]]]+v[i]])
            else:
                try:
                    dp[i+1][j] = max([dp[i][j],dp[i][idx_dict[idxs[j]-w[i]]]+v[i]])
                except:
                    dp[i+1][j] = dp[i][j]
                
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
import sys
import random

def rd():
        return sys.stdin.readline().rstrip()

def rdi():
        return [ long(x) for x in rd().split() ]

m = {}
def update(W, wi, vi):
        if wi > W:
                return
        global m
        ks = m.keys()
        a = set()
        for wj in ks:
                wk = wj + wi
                if wk <= W:
                        vk = m[wj] + vi
                        if wk not in m or m[wk] < vk:
                                m[wk] = vk
                                a.add(wk)
        if wi not in m or m[wi] < vi:
                m[wi] = vi
                a.add(wi)
        for wj in a:
                for wk in ks:
                        if wj in m and wk in m and wk > wj and m[wk] <= m[wj]:
                                del(m[wk])

def calc(W, w, v):
        global m
        m = {}
        for i in range(len(w)):
                update(W, w[i], v[i])
        print max(m.values() + [0])

N, W = rdi()
w = []
v = []
for i in range(N):
        wi, vi = rdi()
        w.append(wi)
        v.append(vi)
calc(W, w, v)

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
v = [[] for i in range(4)]  # w1+x
w1 = -1

for i in range(N):
    a, b = map(int, input().split())
    if i == 0:
        w1 = a
    v[a - w1].append(b)

for i in range(4):
    v[i].reverse()  # 価値の高い順にソート

ret = 0

for i in range(len(v[0]) + 1):
    for j in range(len(v[1]) + 1):
        for k in range(len(v[2]) + 1):
            for l in range(len(v[3]) + 1):
                w = (i + j + k + l) * w1 + (i * 0 + j * 1 + k * 2 + l * 3)
                sum_v = sum(v[0][0:i]) + sum(v[1][0:j]) + sum(v[2][0:k]) + sum(v[3][0:l])
                if w > W or sum_v <= ret:
                    continue
                else:
                    ret = sum_v
                    # print(i, j, k, l)
                    # print(w, ret)

print(ret)