제출 #523077

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
523077		Longgggggggg	Knapsack (NOI18_knapsack)	Java	100 / 100	560 ms	36760 KiB

knapsack

import java.io.*;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.InputMismatchException;

public class knapsack {
    public static void main(String[] args) {
        FastIO io = new FastIO();
        int s = io.nextInt();
        int n = io.nextInt();
        ArrayList<Pair>[] items = new ArrayList[s + 1];
        for (int i = 0; i <= s; i++) items[i] = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int v = io.nextInt();
            int w = io.nextInt();
            int k = io.nextInt();
            items[w].add(new Pair(v, k));
        }
        for (int i = 0; i <= s; i++) items[i].sort(Comparator.comparingInt((a) -> -a.v));


        int[][] dp = new int[s + 1][s + 1];
        for (int i = 1; i <= s; i++) {
            for (int j = 0; j <= s; j++) {
                dp[i][j] = dp[i - 1][j];
                int curSum = j;
                int curVal = 0;
                for (int l = 0; l < items[i].size() && curSum >= i; l++) {
                    for (int amt = 0; amt < items[i].get(l).k && curSum >= i; amt++) {
                        curSum -= i;
                        curVal += items[i].get(l).v;
                        dp[i][j] = Math.max(dp[i - 1][curSum] + curVal, dp[i][j]);
                    }
                }
            }
        }
        io.println(dp[s][s]);
        io.close();
    }

    private static class Pair {
        int v, k;

        public Pair(int v, int k) {
            this.v = v;
            this.k = k;
        }
    }

    private static class FastIO extends PrintWriter {
        private final InputStream stream;
        private final byte[] buf = new byte[1 << 16];
        private int curChar, numChars;

        // standard input
        public FastIO() {
            this(System.in, System.out);
        }

        public FastIO(InputStream i, OutputStream o) {
            super(o);
            stream = i;
        }

        // file input
        public FastIO(String i, String o) throws IOException {
            super(new FileWriter(o));
            stream = new FileInputStream(i);
        }

        // throws InputMismatchException() if previously detected end of file
        private int nextByte() {
            if (numChars == -1) throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars == -1) return -1; // end of file
            }
            return buf[curChar++];
        }

        // to read in entire lines, replace c <= ' '
        // with a function that checks whether c is a line break
        public String next() {
            int c;
            do {
                c = nextByte();
            } while (c <= ' ');
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = nextByte();
            } while (c > ' ');
            return res.toString();
        }

        public int nextInt() { // nextLong() would be implemented similarly
            int c;
            do {
                c = nextByte();
            } while (c <= ' ');
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = nextByte();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res = 10 * res + c - '0';
                c = nextByte();
            } while (c > ' ');
            return res * sgn;
        }

        public long nextLong() { // nextLong() would be implemented similarly
            int c;
            do {
                c = nextByte();
            } while (c <= ' ');
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = nextByte();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res = 10 * res + c - '0';
                c = nextByte();
            } while (c > ' ');
            return res * sgn;
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }

}

컴파일 시 표준 에러 (stderr) 메시지

Note: knapsack.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 27 / 27