提出 #25855795

ソースコード 拡げる

(N,W),*G = $<.map{|ln| ln.split.map(&:to_i) }
W0, = G[0]
V = Array.new(4){[]}
G.each{|w,v| V[w-W0]<<v }
S = V.map{|vs| vs.sort.reverse_each.inject([0]){|s,v| s<<s[-1]+v } }
F = lambda{|i,w|
	x = n = 0
	if si = S[i] and wi = W0+i
		n += j = [w/wi+1,si.size].min
		w -= j*wi
		m0 = nil
		while 0 <= j-=1
			y,m = F[i+1,w+=wi]
			break if m0 == m0=m
			x = y if x < y+=si[j]
			n += m*(N+1)
		end
	end
	next x,n
}
p F[0,W][0]

提出情報

提出日時
問題 D - Simple Knapsack
ユーザ ds14050
言語 Ruby (2.7.1)
得点 400
コード長 444 Byte
結果 AC
実行時間 64 ms
メモリ 14424 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 400 / 400
結果
AC × 4
AC × 16
セット名 テストケース
Sample example0, example1, example2, example3
All antigreedy0, antigreedy1, antigreedy2, example0, example1, example2, example3, quarter0, quarter1, quarter2, rand0, rand1, rand2, smallw0, smallw1, smallw2
ケース名 結果 実行時間 メモリ
antigreedy0 AC 61 ms 14424 KiB
antigreedy1 AC 57 ms 14196 KiB
antigreedy2 AC 55 ms 14108 KiB
example0 AC 57 ms 13988 KiB
example1 AC 57 ms 14228 KiB
example2 AC 59 ms 14172 KiB
example3 AC 55 ms 14056 KiB
quarter0 AC 63 ms 14220 KiB
quarter1 AC 64 ms 14188 KiB
quarter2 AC 59 ms 14196 KiB
rand0 AC 57 ms 14172 KiB
rand1 AC 56 ms 14364 KiB
rand2 AC 61 ms 14320 KiB
smallw0 AC 57 ms 14144 KiB
smallw1 AC 57 ms 14228 KiB
smallw2 AC 59 ms 14260 KiB