Submission #608542

Source Code Expand

items=$<.map{|l|l.split.map{|s|s.to_i}}
n,max=items.shift
vals={0=>0}
items.each{|v,w|
  tmp_vals={}
  vals.each{|wei,val|
    w+wei<=max&&v+val>(vals[w+wei]||0)&&tmp_vals[w+wei]=v+val
  }
  vals.update(tmp_vals){|w,v,tmp_v|v>tmp_v ? v : tmp_v}
}
puts vals.to_a.transpose[1].max

Submission Info

Submission Time
Task D - ナップサック問題
User elysion_halcyon
Language Ruby (2.1.5p273)
Score 34
Code Size 288 Byte
Status TLE
Exec Time 2086 ms
Memory 81372 KiB

Compile Error

./Main.rb:9: warning: shadowing outer local variable - w
./Main.rb:9: warning: shadowing outer local variable - v
./Main.rb:2: warning: assigned but unused variable - n

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3
Score / Max Score 0 / 0 34 / 34 0 / 33 0 / 33
Status
AC × 4
AC × 19
AC × 6
TLE × 11
AC × 6
TLE × 8
Set Name Test Cases
Sample subtask00_sample_1.txt, subtask00_sample_2.txt, subtask00_sample_3.txt, subtask00_sample_4.txt
Subtask1 subtask01_0.txt, subtask01_1.txt, subtask01_10.txt, subtask01_11.txt, subtask01_12.txt, subtask01_13.txt, subtask01_14.txt, subtask01_2.txt, subtask01_3.txt, subtask01_4.txt, subtask01_5.txt, subtask01_6.txt, subtask01_7.txt, subtask01_8.txt, subtask01_9.txt, subtask00_sample_1.txt, subtask00_sample_2.txt, subtask00_sample_3.txt, subtask00_sample_4.txt
Subtask2 subtask02_0.txt, subtask02_1.txt, subtask02_10.txt, subtask02_11.txt, subtask02_12.txt, subtask02_13.txt, subtask02_14.txt, subtask02_2.txt, subtask02_3.txt, subtask02_4.txt, subtask02_5.txt, subtask02_6.txt, subtask02_7.txt, subtask02_8.txt, subtask02_9.txt, subtask00_sample_1.txt, subtask00_sample_3.txt
Subtask3 subtask03_0.txt, subtask03_1.txt, subtask03_10.txt, subtask03_11.txt, subtask03_2.txt, subtask03_3.txt, subtask03_4.txt, subtask03_5.txt, subtask03_6.txt, subtask03_7.txt, subtask03_8.txt, subtask03_9.txt, subtask00_sample_1.txt, subtask00_sample_4.txt
Case Name Status Exec Time Memory
subtask00_sample_1.txt AC 52 ms 4576 KiB
subtask00_sample_2.txt AC 58 ms 4964 KiB
subtask00_sample_3.txt AC 55 ms 4708 KiB
subtask00_sample_4.txt AC 52 ms 4576 KiB
subtask01_0.txt AC 58 ms 4960 KiB
subtask01_1.txt AC 55 ms 4800 KiB
subtask01_10.txt AC 58 ms 4564 KiB
subtask01_11.txt AC 54 ms 4580 KiB
subtask01_12.txt AC 59 ms 4836 KiB
subtask01_13.txt AC 52 ms 4572 KiB
subtask01_14.txt AC 56 ms 4704 KiB
subtask01_2.txt AC 58 ms 4668 KiB
subtask01_3.txt AC 54 ms 4576 KiB
subtask01_4.txt AC 53 ms 4576 KiB
subtask01_5.txt AC 53 ms 4624 KiB
subtask01_6.txt AC 53 ms 4572 KiB
subtask01_7.txt AC 55 ms 4580 KiB
subtask01_8.txt AC 67 ms 5604 KiB
subtask01_9.txt AC 53 ms 4620 KiB
subtask02_0.txt TLE 2043 ms 36964 KiB
subtask02_1.txt TLE 2043 ms 33764 KiB
subtask02_10.txt TLE 2046 ms 33768 KiB
subtask02_11.txt TLE 2041 ms 34784 KiB
subtask02_12.txt TLE 2043 ms 35300 KiB
subtask02_13.txt AC 59 ms 4704 KiB
subtask02_14.txt AC 767 ms 22244 KiB
subtask02_2.txt TLE 2044 ms 37052 KiB
subtask02_3.txt AC 1942 ms 29540 KiB
subtask02_4.txt TLE 2042 ms 35556 KiB
subtask02_5.txt AC 701 ms 22152 KiB
subtask02_6.txt TLE 2050 ms 43836 KiB
subtask02_7.txt TLE 2042 ms 35288 KiB
subtask02_8.txt TLE 2042 ms 33764 KiB
subtask02_9.txt TLE 2043 ms 37132 KiB
subtask03_0.txt AC 255 ms 8672 KiB
subtask03_1.txt TLE 2054 ms 59060 KiB
subtask03_10.txt AC 93 ms 5096 KiB
subtask03_11.txt AC 53 ms 4580 KiB
subtask03_2.txt TLE 2042 ms 35044 KiB
subtask03_3.txt TLE 2086 ms 55520 KiB
subtask03_4.txt TLE 2050 ms 69852 KiB
subtask03_5.txt TLE 2050 ms 66648 KiB
subtask03_6.txt AC 123 ms 6248 KiB
subtask03_7.txt TLE 2051 ms 80212 KiB
subtask03_8.txt TLE 2050 ms 81372 KiB
subtask03_9.txt TLE 2050 ms 73428 KiB