結果

問題 No.527 ナップサック容量問題
ユーザー 双六双六
提出日時 2020-08-26 15:49:36
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 356 ms / 2,000 ms
コード長 765 bytes
コンパイル時間 310 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 222,464 KB
最終ジャッジ日時 2024-11-07 12:02:12
合計ジャッジ時間 8,420 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 61 ms
66,688 KB
testcase_01 AC 63 ms
68,224 KB
testcase_02 AC 58 ms
64,896 KB
testcase_03 AC 62 ms
67,968 KB
testcase_04 AC 57 ms
63,232 KB
testcase_05 AC 164 ms
128,256 KB
testcase_06 AC 306 ms
199,680 KB
testcase_07 AC 246 ms
173,056 KB
testcase_08 AC 144 ms
119,552 KB
testcase_09 AC 64 ms
63,744 KB
testcase_10 AC 301 ms
202,112 KB
testcase_11 AC 206 ms
159,488 KB
testcase_12 AC 168 ms
133,888 KB
testcase_13 AC 322 ms
204,288 KB
testcase_14 AC 137 ms
115,328 KB
testcase_15 AC 192 ms
145,024 KB
testcase_16 AC 60 ms
68,096 KB
testcase_17 AC 170 ms
131,840 KB
testcase_18 AC 182 ms
141,312 KB
testcase_19 AC 63 ms
69,632 KB
testcase_20 AC 141 ms
118,400 KB
testcase_21 AC 356 ms
222,464 KB
testcase_22 AC 230 ms
169,472 KB
testcase_23 AC 329 ms
218,880 KB
testcase_24 AC 106 ms
95,872 KB
testcase_25 AC 224 ms
166,016 KB
testcase_26 AC 219 ms
155,904 KB
testcase_27 AC 215 ms
157,440 KB
testcase_28 AC 187 ms
144,128 KB
testcase_29 AC 352 ms
222,080 KB
testcase_30 AC 71 ms
76,288 KB
testcase_31 AC 149 ms
131,200 KB
testcase_32 AC 169 ms
147,072 KB
testcase_33 AC 158 ms
134,272 KB
testcase_34 AC 173 ms
150,144 KB
testcase_35 AC 204 ms
152,576 KB
testcase_36 AC 59 ms
66,688 KB
testcase_37 AC 164 ms
129,792 KB
testcase_38 AC 191 ms
147,200 KB
testcase_39 AC 181 ms
141,056 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	DP = [[-INF for i in range(100001)] for j in range(N + 1)]
	DP[0][0] = 0
	for i in range(N):
		v, w = getlist()
		for j in range(100001):
			if DP[i][j] != -INF:
				DP[i + 1][j] = max(DP[i][j], DP[i + 1][j]) 
				DP[i + 1][j + w] = max(DP[i + 1][j + w], DP[i][j] + v)

	V = int(input())
	m = INF
	M = INF
	for i in range(100001):
		if DP[-1][i] >= V:
			m = min(m, i)

		if DP[-1][i] > V and M == INF:
			M = i - 1

	m = max(1, m)
	if M == INF:
		M = "inf"

	print(m)
	print(M)

if __name__ == '__main__':
	main()
0