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
AC × 4
AC × 19
AC × 17
AC × 14
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