提出 #17935118

ソースコード 拡げる

# まだよくわからない。 https://atcoder.jp/contests/abc015/submissions/11417636

(W,),(N,K),*AB = $<.map{|ln| ln.split.map(&:to_i) }
AB.reject!{|a,| W<a }
AB.sort_by!{_2}
Vmax = AB.sum{_2}

幅 = [[W+1]*(Vmax+1)]
幅[0][0] = vsum = 0
AB.each.with_index(2){|(a,b),n|
	幅 << 幅[-1].dup unless K < 幅.size
	幅.each_cons(2).reverse_each{|k,k1|
		k[0,vsum+1].each.with_index(b){|w,v|
			k1[v] = w+a if w+a < k1[v]
		}
	}
	vsum += b
}

p Vmax.downto(0).find{|v| 幅.any?{|k| k[v]<=W } }

提出情報

提出日時
問題 D - 高橋くんの苦悩
ユーザ ds14050
言語 Ruby (2.7.1)
得点 100
コード長 514 Byte
結果 AC
実行時間 111 ms
メモリ 24292 KiB

ジャッジ結果

セット名 All
得点 / 配点 100 / 100
結果
AC × 47
セット名 テストケース
All sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt, test_34.txt, test_35.txt, test_36.txt, test_37.txt, test_38.txt, test_39.txt, test_40.txt, test_41.txt
ケース名 結果 実行時間 メモリ
sample_01.txt AC 61 ms 14284 KiB
sample_02.txt AC 57 ms 14400 KiB
sample_03.txt AC 60 ms 14364 KiB
test_01.txt AC 97 ms 22408 KiB
test_02.txt AC 61 ms 14280 KiB
test_03.txt AC 61 ms 14248 KiB
test_04.txt AC 58 ms 14320 KiB
test_05.txt AC 60 ms 14532 KiB
test_06.txt AC 59 ms 14252 KiB
test_07.txt AC 62 ms 15636 KiB
test_08.txt AC 62 ms 14980 KiB
test_09.txt AC 58 ms 14664 KiB
test_10.txt AC 68 ms 16980 KiB
test_11.txt AC 71 ms 16948 KiB
test_12.txt AC 63 ms 15248 KiB
test_13.txt AC 63 ms 15520 KiB
test_14.txt AC 64 ms 15048 KiB
test_15.txt AC 97 ms 22528 KiB
test_16.txt AC 77 ms 17800 KiB
test_17.txt AC 94 ms 22136 KiB
test_18.txt AC 84 ms 20424 KiB
test_19.txt AC 58 ms 15104 KiB
test_20.txt AC 85 ms 20588 KiB
test_21.txt AC 72 ms 17908 KiB
test_22.txt AC 62 ms 15244 KiB
test_23.txt AC 66 ms 17628 KiB
test_24.txt AC 96 ms 21984 KiB
test_25.txt AC 66 ms 16048 KiB
test_26.txt AC 94 ms 22656 KiB
test_27.txt AC 56 ms 14252 KiB
test_28.txt AC 59 ms 14268 KiB
test_29.txt AC 58 ms 14336 KiB
test_30.txt AC 81 ms 20840 KiB
test_31.txt AC 58 ms 14444 KiB
test_32.txt AC 80 ms 20624 KiB
test_33.txt AC 111 ms 24248 KiB
test_34.txt AC 73 ms 17140 KiB
test_35.txt AC 107 ms 24292 KiB
test_36.txt AC 81 ms 19536 KiB
test_37.txt AC 59 ms 14884 KiB
test_38.txt AC 80 ms 19356 KiB
test_39.txt AC 81 ms 21084 KiB
test_40.txt AC 68 ms 16284 KiB
test_41.txt AC 85 ms 20924 KiB