提出 #58243889

ソースコード 拡げる

(N,W),*P = $<.map {_1.split.map &:to_i}
H = Hash.new 0
H[0] = 0
P.sort_by {(-_2 << 20) / _1.to_r + _1}.each {|w,v|
  H.keys.sort.reverse_each {|k|
    c,u = 0,H[k]
    H[k] = u+(v-c)*c while W >= k+=w and H[k] < u+v*(c+=1) -c*c 
  }
}
p H.values.max

提出情報

提出日時
問題 F - Knapsack with Diminishing Values
ユーザ l0rzl
言語 Ruby (ruby 3.2.2)
得点 550
コード長 258 Byte
結果 AC
実行時間 1429 ms
メモリ 115836 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 550 / 550
結果
AC × 3
AC × 58
セット名 テストケース
Sample 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt
All 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt, 01_random_20.txt, 01_random_21.txt, 01_random_22.txt, 01_random_23.txt, 01_random_24.txt, 01_random_25.txt, 01_random_26.txt, 01_random_27.txt, 01_random_28.txt, 01_random_29.txt, 01_random_30.txt, 01_random_31.txt, 01_random_32.txt, 01_random_33.txt, 01_random_34.txt, 01_random_35.txt, 01_random_36.txt, 01_random_37.txt, 01_random_38.txt, 01_random_39.txt, 01_random_40.txt, 01_random_41.txt, 01_random_42.txt, 01_random_43.txt, 01_random_44.txt, 01_random_45.txt, 01_random_46.txt, 01_random_47.txt, 01_random_48.txt, 01_random_49.txt, 01_random_50.txt, 02_handmade_01.txt, 02_handmade_02.txt, 02_handmade_03.txt, 02_handmade_04.txt, 02_handmade_05.txt
ケース名 結果 実行時間 メモリ
00_sample_01.txt AC 42 ms 17160 KiB
00_sample_02.txt AC 42 ms 17280 KiB
00_sample_03.txt AC 42 ms 17204 KiB
01_random_01.txt AC 967 ms 115432 KiB
01_random_02.txt AC 961 ms 115592 KiB
01_random_03.txt AC 964 ms 115596 KiB
01_random_04.txt AC 956 ms 115632 KiB
01_random_05.txt AC 957 ms 115836 KiB
01_random_06.txt AC 74 ms 21580 KiB
01_random_07.txt AC 863 ms 95508 KiB
01_random_08.txt AC 668 ms 76116 KiB
01_random_09.txt AC 1153 ms 115668 KiB
01_random_10.txt AC 89 ms 29232 KiB
01_random_11.txt AC 912 ms 88532 KiB
01_random_12.txt AC 353 ms 54696 KiB
01_random_13.txt AC 1254 ms 102156 KiB
01_random_14.txt AC 1429 ms 115556 KiB
01_random_15.txt AC 870 ms 63840 KiB
01_random_16.txt AC 106 ms 26552 KiB
01_random_17.txt AC 316 ms 55292 KiB
01_random_18.txt AC 54 ms 19052 KiB
01_random_19.txt AC 998 ms 115544 KiB
01_random_20.txt AC 660 ms 85592 KiB
01_random_21.txt AC 106 ms 25232 KiB
01_random_22.txt AC 157 ms 32988 KiB
01_random_23.txt AC 449 ms 66068 KiB
01_random_24.txt AC 1107 ms 115584 KiB
01_random_25.txt AC 139 ms 30040 KiB
01_random_26.txt AC 296 ms 47056 KiB
01_random_27.txt AC 371 ms 56968 KiB
01_random_28.txt AC 469 ms 47880 KiB
01_random_29.txt AC 1184 ms 115724 KiB
01_random_30.txt AC 287 ms 47972 KiB
01_random_31.txt AC 155 ms 34588 KiB
01_random_32.txt AC 197 ms 39172 KiB
01_random_33.txt AC 223 ms 44800 KiB
01_random_34.txt AC 1000 ms 115728 KiB
01_random_35.txt AC 110 ms 27568 KiB
01_random_36.txt AC 244 ms 46656 KiB
01_random_37.txt AC 752 ms 99640 KiB
01_random_38.txt AC 213 ms 42132 KiB
01_random_39.txt AC 996 ms 115660 KiB
01_random_40.txt AC 297 ms 55788 KiB
01_random_41.txt AC 248 ms 46968 KiB
01_random_42.txt AC 133 ms 31844 KiB
01_random_43.txt AC 659 ms 94192 KiB
01_random_44.txt AC 865 ms 115828 KiB
01_random_45.txt AC 132 ms 28392 KiB
01_random_46.txt AC 317 ms 48264 KiB
01_random_47.txt AC 236 ms 48912 KiB
01_random_48.txt AC 82 ms 22576 KiB
01_random_49.txt AC 869 ms 115768 KiB
01_random_50.txt AC 76 ms 26272 KiB
02_handmade_01.txt AC 48 ms 17896 KiB
02_handmade_02.txt AC 78 ms 25984 KiB
02_handmade_03.txt AC 67 ms 23424 KiB
02_handmade_04.txt AC 578 ms 61264 KiB
02_handmade_05.txt AC 98 ms 31408 KiB