結果
問題 |
No.527 ナップサック容量問題
|
ユーザー |
![]() |
提出日時 | 2022-10-14 15:31:25 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 246 ms / 2,000 ms |
コード長 | 2,034 bytes |
コンパイル時間 | 2,095 ms |
コンパイル使用メモリ | 78,780 KB |
実行使用メモリ | 45,912 KB |
最終ジャッジ日時 | 2024-06-26 12:38:34 |
合計ジャッジ時間 | 7,428 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(); int n = sc.nextInt(); TreeMap<Integer, Integer> values = new TreeMap<>(); values.put(0, 0); for (int i = 0; i < n; i++) { int v = sc.nextInt(); int w = sc.nextInt(); Integer key = Integer.MAX_VALUE; while ((key = values.lowerKey(key)) != null) { Integer next = key + v; int wnext = values.get(key) + w; if (values.lastKey() < next || values.ceilingEntry(next).getValue() > wnext) { values.put(next, wnext); } while ((next = values.lowerKey(next)) != null) { if (values.get(next) >= wnext) { values.remove(next); } else { break; } } } } values.put(0, 1); int v = sc.nextInt(); System.out.println(values.get(v)); if (values.lastKey() == v) { System.out.println("inf"); } else { System.out.println(values.higherEntry(v).getValue() - 1); } } } class Scanner { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(""); StringBuilder sb = new StringBuilder(); public Scanner() throws Exception { } public int nextInt() throws Exception { return Integer.parseInt(next()); } public long nextLong() throws Exception { return Long.parseLong(next()); } public double nextDouble() throws Exception { return Double.parseDouble(next()); } public String next() throws Exception { while (!st.hasMoreTokens()) { st = new StringTokenizer(br.readLine()); } return st.nextToken(); } }