結果

問題 No.527 ナップサック容量問題
ユーザー schwarzahlschwarzahl
提出日時 2017-06-10 04:54:26
言語 Java21
(openjdk 21)
結果
AC  
実行時間 771 ms / 2,000 ms
コード長 2,225 bytes
コンパイル時間 3,217 ms
コンパイル使用メモリ 81,644 KB
実行使用メモリ 67,576 KB
最終ジャッジ日時 2023-10-24 06:14:09
合計ジャッジ時間 15,979 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 135 ms
42,908 KB
testcase_01 AC 139 ms
43,208 KB
testcase_02 AC 121 ms
41,408 KB
testcase_03 AC 127 ms
42,700 KB
testcase_04 AC 129 ms
41,764 KB
testcase_05 AC 302 ms
56,044 KB
testcase_06 AC 674 ms
60,236 KB
testcase_07 AC 456 ms
57,668 KB
testcase_08 AC 256 ms
52,792 KB
testcase_09 AC 139 ms
41,980 KB
testcase_10 AC 684 ms
59,012 KB
testcase_11 AC 448 ms
67,576 KB
testcase_12 AC 303 ms
56,096 KB
testcase_13 AC 771 ms
60,476 KB
testcase_14 AC 261 ms
53,332 KB
testcase_15 AC 328 ms
57,264 KB
testcase_16 AC 134 ms
42,920 KB
testcase_17 AC 291 ms
56,268 KB
testcase_18 AC 340 ms
57,508 KB
testcase_19 AC 124 ms
42,836 KB
testcase_20 AC 205 ms
46,756 KB
testcase_21 AC 327 ms
57,424 KB
testcase_22 AC 244 ms
47,208 KB
testcase_23 AC 286 ms
50,784 KB
testcase_24 AC 181 ms
45,804 KB
testcase_25 AC 152 ms
45,456 KB
testcase_26 AC 202 ms
46,072 KB
testcase_27 AC 182 ms
46,316 KB
testcase_28 AC 154 ms
45,576 KB
testcase_29 AC 237 ms
46,220 KB
testcase_30 AC 135 ms
44,760 KB
testcase_31 AC 156 ms
46,020 KB
testcase_32 AC 195 ms
46,268 KB
testcase_33 AC 169 ms
45,796 KB
testcase_34 AC 163 ms
45,316 KB
testcase_35 AC 389 ms
57,272 KB
testcase_36 AC 124 ms
41,932 KB
testcase_37 AC 274 ms
53,064 KB
testcase_38 AC 310 ms
56,100 KB
testcase_39 AC 327 ms
56,864 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

public class Main {
	public static void main(String[] args){
		Main main = new Main();
		main.solveC();
	}

	private void solveA() {
		Scanner sc = new Scanner(System.in);
		String line = sc.nextLine();
		int h = c2i(line.charAt(0)) * 10 + c2i(line.charAt(1));
		int m = c2i(line.charAt(3)) * 10 + c2i(line.charAt(4));
		m += 5;
		if (m >= 60) {
			m -= 60;
			h += 1;
			h = h % 24;
		}
		System.out.printf("%02d:%02d", h, m);
	}

	private int c2i(char c) {
		return c - '0';
	}

	private void solveB() {
		Scanner sc = new Scanner(System.in);
		long N = sc.nextLong();
		long M = sc.nextLong();

		long pp = 0;
		long p = 1;
		for (int n = 3; n <= N; n++) {
			long now = (pp + p) % M;
			pp = p;
			p = now;
		}
		System.out.println(p);
	}

	private void solveC() {
		Scanner sc = new Scanner(System.in);
		final int MAX_W = 100001;

		int N = sc.nextInt();
		List<Budget> list = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			Budget b = new Budget();
			b.v = sc.nextInt();
			b.w = sc.nextInt();
			list.add(b);
		}
		int V = sc.nextInt();

		int[] values = new int[MAX_W];

		Set<Integer> set = new HashSet<>();
		set.add(0);
		for (Budget b : list) {
			int[] nextValues = Arrays.copyOf(values, MAX_W);
			Set<Integer> next_set = new HashSet<>();
			for (int weight : set) {
				int tmp_v = values[weight];
				int next_v = tmp_v + b.v;
				int next_w = weight + b.w;
				if (next_v > nextValues[next_w]) {
					nextValues[next_w] = next_v;
					if (next_v <= V) {
						next_set.add(next_w);
					}
				}
				next_set.add(weight);
			}
			set = next_set;
			values = nextValues;
		}
		int min = 1;
		Integer max = null;
		for (int wi = 0; wi < 100001; wi++) {
			if (min == 1 && V > 0 && values[wi] == V) {
				min = wi;
			}
			if (max == null && values[wi] > V) {
				max = wi;
			}
		}
		System.out.println(min);
		System.out.println(max == null ? "inf" : max - 1);
	}

	class Budget {
		int v;
		int w;

		public int getValue() {
			return v;
		}

		public int getWeight() {
			return w;
		}
	}
}
0