Submission #5553945
Source Code Expand
import java.util.*; public class Main { private static final long INF = 200 * 1000000000L + 1; int n, lw; long v[], w[]; public void main(Scanner sc) { n = sc.nextInt(); lw = sc.nextInt(); v = new long[n]; w = new long[n]; for (int i = 0; i < n; i++) { v[i] = sc.nextInt(); w[i] = sc.nextInt(); } long maxValue = Arrays.stream(v).max().getAsLong(); long maxWeight = Arrays.stream(w).max().getAsLong(); if (maxValue <= 1000) { System.out.println(knap1((int) maxValue)); } else if (maxWeight <= 1000) { System.out.println(knap2()); } else { System.out.println(knap3()); } } private long knap1(int mv) { long dp[] = new long[n * mv + 1]; Arrays.fill(dp, INF); dp[0] = 0; for (int i = 0; i < n; i++) { int vi = (int) v[i]; for (int j = n * mv; j >= vi; j--) { dp[j] = Math.min(dp[j], dp[j - vi] + w[i]); } } long ans = 0; for (int i = 0; i <= n * mv; i++) { if (dp[i] <= lw) { ans = i; } } return ans; } private long knap2() { long dp[][] = new long[n + 1][lw + 1]; for (int i = 1; i <= n; i++) { int wi = (int) w[i - 1]; for (int j = 0; j <= lw; j++) { dp[i][j] = (j < wi) ? dp[i - 1][j] : Math.max(dp[i - 1][j], dp[i - 1][j - wi] + v[i - 1]); } } return dp[n][lw]; } private long knap3() { int n1 = n / 2; int n2 = n - n1; Map<Long, Long> wv1 = new TreeMap<>((v1, v2) -> Long.compare(v1, v2)); Map<Long, Long> wv2 = new TreeMap<>((v1, v2) -> Long.compare(v1, v2)); for (int i = 0; i < (1 << n1); i++) { long sumW = 0, sumV = 0; for (int j = 0; j < n1; j++) { if ((i >> j) % 2 == 1) { sumW += w[j]; sumV += v[j]; } } wv1.put(sumV, Math.max(wv1.getOrDefault(sumV, 0L), sumW)); } for (int i = 0; i < (1 << n2); i++) { long sumW = 0, sumV = 0; for (int j = 0; j < n2; j++) { if ((i >> j) % 2 == 1) { sumW += w[j + n1]; sumV += v[j + n1]; } } wv2.put(sumV, Math.max(wv2.getOrDefault(sumV, 0L), sumW)); } long ans = 0; for (Map.Entry<Long, Long> entry1 : wv1.entrySet()) { long nw1 = entry1.getValue(); long nv1 = entry1.getKey(); if (nw1 > lw) { continue; } for (Map.Entry<Long, Long> entry2 : wv2.entrySet()) { long nw2 = entry2.getValue(); if (nw1 + nw2 > lw) { continue; } ans = Math.max(ans, nv1 + entry2.getKey()); } } return ans; } public static void main(String[] args) throws Exception { try (Scanner sc = new Scanner(System.in)) { new Main().main(sc); } catch (Exception e) { throw e; } } }
Submission Info
Submission Time | |
---|---|
Task | D - ナップサック問題 |
User | minorin |
Language | Java8 (OpenJDK 1.8.0) |
Score | 100 |
Code Size | 3470 Byte |
Status | AC |
Exec Time | 474 ms |
Memory | 247636 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | Subtask3 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 34 / 34 | 33 / 33 | 33 / 33 | ||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | subtask00_sample_1.txt, subtask00_sample_2.txt, subtask00_sample_3.txt, subtask00_sample_4.txt |
Subtask1 | subtask01_0.txt, subtask01_1.txt, subtask01_10.txt, subtask01_11.txt, subtask01_12.txt, subtask01_13.txt, subtask01_14.txt, subtask01_2.txt, subtask01_3.txt, subtask01_4.txt, subtask01_5.txt, subtask01_6.txt, subtask01_7.txt, subtask01_8.txt, subtask01_9.txt, subtask00_sample_1.txt, subtask00_sample_2.txt, subtask00_sample_3.txt, subtask00_sample_4.txt |
Subtask2 | subtask02_0.txt, subtask02_1.txt, subtask02_10.txt, subtask02_11.txt, subtask02_12.txt, subtask02_13.txt, subtask02_14.txt, subtask02_2.txt, subtask02_3.txt, subtask02_4.txt, subtask02_5.txt, subtask02_6.txt, subtask02_7.txt, subtask02_8.txt, subtask02_9.txt, subtask00_sample_1.txt, subtask00_sample_3.txt |
Subtask3 | subtask03_0.txt, subtask03_1.txt, subtask03_10.txt, subtask03_11.txt, subtask03_2.txt, subtask03_3.txt, subtask03_4.txt, subtask03_5.txt, subtask03_6.txt, subtask03_7.txt, subtask03_8.txt, subtask03_9.txt, subtask00_sample_1.txt, subtask00_sample_4.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask00_sample_1.txt | AC | 222 ms | 26324 KB |
subtask00_sample_2.txt | AC | 379 ms | 33720 KB |
subtask00_sample_3.txt | AC | 175 ms | 26836 KB |
subtask00_sample_4.txt | AC | 180 ms | 26320 KB |
subtask01_0.txt | AC | 366 ms | 33900 KB |
subtask01_1.txt | AC | 436 ms | 35312 KB |
subtask01_10.txt | AC | 384 ms | 31604 KB |
subtask01_11.txt | AC | 351 ms | 31944 KB |
subtask01_12.txt | AC | 474 ms | 36692 KB |
subtask01_13.txt | AC | 371 ms | 33152 KB |
subtask01_14.txt | AC | 450 ms | 35168 KB |
subtask01_2.txt | AC | 337 ms | 33272 KB |
subtask01_3.txt | AC | 348 ms | 33236 KB |
subtask01_4.txt | AC | 255 ms | 29152 KB |
subtask01_5.txt | AC | 183 ms | 25044 KB |
subtask01_6.txt | AC | 176 ms | 26836 KB |
subtask01_7.txt | AC | 338 ms | 31208 KB |
subtask01_8.txt | AC | 454 ms | 33644 KB |
subtask01_9.txt | AC | 352 ms | 31732 KB |
subtask02_0.txt | AC | 366 ms | 247636 KB |
subtask02_1.txt | AC | 221 ms | 53076 KB |
subtask02_10.txt | AC | 221 ms | 52944 KB |
subtask02_11.txt | AC | 276 ms | 83280 KB |
subtask02_12.txt | AC | 280 ms | 127184 KB |
subtask02_13.txt | AC | 193 ms | 24404 KB |
subtask02_14.txt | AC | 221 ms | 34900 KB |
subtask02_2.txt | AC | 315 ms | 164684 KB |
subtask02_3.txt | AC | 233 ms | 55636 KB |
subtask02_4.txt | AC | 335 ms | 159944 KB |
subtask02_5.txt | AC | 210 ms | 33364 KB |
subtask02_6.txt | AC | 317 ms | 164436 KB |
subtask02_7.txt | AC | 278 ms | 130512 KB |
subtask02_8.txt | AC | 226 ms | 53716 KB |
subtask02_9.txt | AC | 324 ms | 164560 KB |
subtask03_0.txt | AC | 305 ms | 28368 KB |
subtask03_1.txt | AC | 307 ms | 28628 KB |
subtask03_10.txt | AC | 301 ms | 27092 KB |
subtask03_11.txt | AC | 197 ms | 25044 KB |
subtask03_2.txt | AC | 313 ms | 28756 KB |
subtask03_3.txt | AC | 310 ms | 26952 KB |
subtask03_4.txt | AC | 298 ms | 26192 KB |
subtask03_5.txt | AC | 313 ms | 26836 KB |
subtask03_6.txt | AC | 303 ms | 27604 KB |
subtask03_7.txt | AC | 308 ms | 28880 KB |
subtask03_8.txt | AC | 320 ms | 26704 KB |
subtask03_9.txt | AC | 305 ms | 26324 KB |