oj.uz

Submission #523077

# Submission time Handle Problem Language Result Execution time Memory
523077 2022-02-07T01:22:41 Z Longgggggggg Knapsack (NOI18_knapsack) Java 11
100 / 100
 560 ms 36760 KB 
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());
        }
    }

}

Compilation message

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

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 18508 KB Output is correct
2 Correct 102 ms 18704 KB Output is correct
3 Correct 121 ms 18688 KB Output is correct
4 Correct 91 ms 17716 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 9084 KB Output is correct
2 Correct 133 ms 28620 KB Output is correct
3 Correct 137 ms 28512 KB Output is correct
4 Correct 116 ms 28516 KB Output is correct
5 Correct 114 ms 28656 KB Output is correct
6 Correct 130 ms 28952 KB Output is correct
7 Correct 116 ms 28852 KB Output is correct
8 Correct 124 ms 28668 KB Output is correct
9 Correct 119 ms 28880 KB Output is correct
10 Correct 130 ms 28740 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 9084 KB Output is correct
2 Correct 133 ms 28620 KB Output is correct
3 Correct 137 ms 28512 KB Output is correct
4 Correct 116 ms 28516 KB Output is correct
5 Correct 114 ms 28656 KB Output is correct
6 Correct 130 ms 28952 KB Output is correct
7 Correct 116 ms 28852 KB Output is correct
8 Correct 124 ms 28668 KB Output is correct
9 Correct 119 ms 28880 KB Output is correct
10 Correct 130 ms 28740 KB Output is correct
11 Correct 75 ms 8968 KB Output is correct
12 Correct 156 ms 28704 KB Output is correct
13 Correct 137 ms 28968 KB Output is correct
14 Correct 120 ms 28548 KB Output is correct
15 Correct 129 ms 28604 KB Output is correct
16 Correct 136 ms 29072 KB Output is correct
17 Correct 116 ms 28808 KB Output is correct
18 Correct 136 ms 28824 KB Output is correct
19 Correct 139 ms 28636 KB Output is correct
20 Correct 135 ms 28716 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 18508 KB Output is correct
2 Correct 102 ms 18704 KB Output is correct
3 Correct 121 ms 18688 KB Output is correct
4 Correct 91 ms 17716 KB Output is correct
5 Correct 72 ms 9084 KB Output is correct
6 Correct 133 ms 28620 KB Output is correct
7 Correct 137 ms 28512 KB Output is correct
8 Correct 116 ms 28516 KB Output is correct
9 Correct 114 ms 28656 KB Output is correct
10 Correct 130 ms 28952 KB Output is correct
11 Correct 116 ms 28852 KB Output is correct
12 Correct 124 ms 28668 KB Output is correct
13 Correct 119 ms 28880 KB Output is correct
14 Correct 130 ms 28740 KB Output is correct
15 Correct 75 ms 8968 KB Output is correct
16 Correct 156 ms 28704 KB Output is correct
17 Correct 137 ms 28968 KB Output is correct
18 Correct 120 ms 28548 KB Output is correct
19 Correct 129 ms 28604 KB Output is correct
20 Correct 136 ms 29072 KB Output is correct
21 Correct 116 ms 28808 KB Output is correct
22 Correct 136 ms 28824 KB Output is correct
23 Correct 139 ms 28636 KB Output is correct
24 Correct 135 ms 28716 KB Output is correct
25 Correct 68 ms 8860 KB Output is correct
26 Correct 142 ms 28980 KB Output is correct
27 Correct 133 ms 28592 KB Output is correct
28 Correct 120 ms 28760 KB Output is correct
29 Correct 114 ms 28748 KB Output is correct
30 Correct 142 ms 29216 KB Output is correct
31 Correct 117 ms 28608 KB Output is correct
32 Correct 137 ms 28820 KB Output is correct
33 Correct 139 ms 29096 KB Output is correct
34 Correct 161 ms 29312 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 18508 KB Output is correct
2 Correct 102 ms 18704 KB Output is correct
3 Correct 121 ms 18688 KB Output is correct
4 Correct 91 ms 17716 KB Output is correct
5 Correct 72 ms 9084 KB Output is correct
6 Correct 133 ms 28620 KB Output is correct
7 Correct 137 ms 28512 KB Output is correct
8 Correct 116 ms 28516 KB Output is correct
9 Correct 114 ms 28656 KB Output is correct
10 Correct 130 ms 28952 KB Output is correct
11 Correct 116 ms 28852 KB Output is correct
12 Correct 124 ms 28668 KB Output is correct
13 Correct 119 ms 28880 KB Output is correct
14 Correct 130 ms 28740 KB Output is correct
15 Correct 75 ms 8968 KB Output is correct
16 Correct 156 ms 28704 KB Output is correct
17 Correct 137 ms 28968 KB Output is correct
18 Correct 120 ms 28548 KB Output is correct
19 Correct 129 ms 28604 KB Output is correct
20 Correct 136 ms 29072 KB Output is correct
21 Correct 116 ms 28808 KB Output is correct
22 Correct 136 ms 28824 KB Output is correct
23 Correct 139 ms 28636 KB Output is correct
24 Correct 135 ms 28716 KB Output is correct
25 Correct 68 ms 8860 KB Output is correct
26 Correct 142 ms 28980 KB Output is correct
27 Correct 133 ms 28592 KB Output is correct
28 Correct 120 ms 28760 KB Output is correct
29 Correct 114 ms 28748 KB Output is correct
30 Correct 142 ms 29216 KB Output is correct
31 Correct 117 ms 28608 KB Output is correct
32 Correct 137 ms 28820 KB Output is correct
33 Correct 139 ms 29096 KB Output is correct
34 Correct 161 ms 29312 KB Output is correct
35 Correct 279 ms 19068 KB Output is correct
36 Correct 407 ms 34248 KB Output is correct
37 Correct 368 ms 33932 KB Output is correct
38 Correct 385 ms 35528 KB Output is correct
39 Correct 371 ms 36460 KB Output is correct
40 Correct 381 ms 36428 KB Output is correct
41 Correct 437 ms 35436 KB Output is correct
42 Correct 420 ms 35488 KB Output is correct
43 Correct 476 ms 35412 KB Output is correct
44 Correct 538 ms 35596 KB Output is correct
45 Correct 313 ms 36760 KB Output is correct
46 Correct 194 ms 36068 KB Output is correct
47 Correct 560 ms 36660 KB Output is correct
48 Correct 527 ms 36420 KB Output is correct
49 Correct 226 ms 36496 KB Output is correct
50 Correct 350 ms 36096 KB Output is correct