Submission #842393

#	Time	Username	Problem	Language	Result	Execution time	Memory
842393		space_man	Knapsack (NOI18_knapsack)	Java	100 / 100	499 ms	70212 KiB

knapsack

import java.io.*;
import java.util.*;

import static java.lang.System.exit;

public class knapsack {
    static FastIO in;
    static PrintWriter out;
    static boolean multiTests = false;
    static boolean fileIO = false;

    void solve(int tNum) throws IOException {
        int s = in.nextInt(), n = in.nextInt();
        HashMap<Integer, ArrayList<Pair>> inventory = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int v = in.nextInt(), w = in.nextInt(), c = in.nextInt();
            if(!inventory.containsKey(w)) inventory.put(w, new ArrayList<>());
            inventory.get(w).add(new Pair(v, c));
        }
        
        long[][] dp = new long[inventory.size() + 1][s + 1];
        for (long[] longs : dp) {
            Arrays.fill(longs, Integer.MIN_VALUE);
        }
        dp[0][0] = 0;
        int id = 1;
        for (Map.Entry<Integer, ArrayList<Pair>> entry : inventory.entrySet()) {
            int w = entry.getKey();
            ArrayList<Pair> list = entry.getValue();
            list.sort(Comparator.comparingInt(p -> -p.cost));
            for (int i = 0; i <= s; i++) {
                dp[id][i] = dp[id - 1][i];
                int taken = 0, index = 0, currTaken = 0;
                long total = 0L;
                while ((taken + 1) * w <= i && index < list.size()) {
                    taken++;
                    total += list.get(index).cost;
                    if(dp[id-1][i - w * taken] != Integer.MIN_VALUE) {
                        dp[id][i] = Math.max(dp[id][i], dp[id-1][i - w * taken] + total);
                    }
                    currTaken++;
                    if(currTaken == list.get(index).count) {
                        index++;
                        currTaken = 0;
                    }
                }
            }
            id++;
        }
        long ans = Integer.MIN_VALUE;
        for (int i = 0; i <= s; i++) {
            ans = Math.max(ans, dp[inventory.size()][i]);
        }
        out.println(ans);
    }
    
    static class Pair {
        int cost, count;

        public Pair(int cost, int count) {
            this.cost = cost;
            this.count = count;
        }
    }

    public static void main(String[] args) {
        try {
            in = fileIO ? new FastIO(".in") : new FastIO();
            out = fileIO ? new PrintWriter(new BufferedWriter(new FileWriter(".out"))) : new PrintWriter(System.out);
            knapsack closing = new knapsack();
            int T = multiTests ? in.nextInt() : 1;
            for (int t = 1; t <= T; t++) {
                closing.solve(t);
            }
            in.close();
            out.close();
        } catch (IOException e) {
            e.printStackTrace();
            exit(1);
        }
    }

    static class FastIO implements AutoCloseable {
        private DataInputStream din;
        private byte[] buffer;
        private int pointer, bytesRead;

        public FastIO() {
            this(new DataInputStream(System.in));
        }

        public FastIO(String filename) throws FileNotFoundException {
            this(new DataInputStream(new FileInputStream(filename)));
        }

        private FastIO(DataInputStream din) {
            this.din = din;
            buffer = new byte[1 << 17];
            pointer = bytesRead = 0;
        }

        public int nextInt() throws IOException {
            int r = 0;
            byte b;
            do {
                b = nextByte();
            } while (b <= ' ');

            boolean negative = false;
            if (b == '-') {
                negative = true;
                b = nextByte();
            }

            while (b >= '0' && b <= '9') {
                r = 10 * r + b - '0';
                b = nextByte();
            }

            return (negative) ? -r : r;
        }

        public long nextLong() throws IOException {
            long r = 0;
            byte b;
            do {
                b = nextByte();
            } while (b <= ' ');

            boolean negative = false;
            if (b == '-') {
                negative = true;
                b = nextByte();
            }

            while (b >= '0' && b <= '9') {
                r = 10 * r + b - '0';
                b = nextByte();
            }

            return (negative) ? -r : r;
        }

        public double nextDouble() throws IOException {
            double r = 0, d = 1;
            byte b;
            do {
                b = nextByte();
            } while (b <= ' ');

            boolean negative = false;
            if (b == '-') {
                negative = true;
                b = nextByte();
            }

            while (b >= '0' && b <= '9') {
                r = 10 * r + b - '0';
                b = nextByte();
            }

            if (b == '.') {
                b = nextByte();
                while (b >= '0' && b <= '9') {
                    r += (b - '0') / (d *= 10);
                    b = nextByte();
                }
            }

            return (negative) ? -r : r;
        }

        public String next() throws IOException {
            StringBuffer ret = new StringBuffer();
            byte b;

            do {
                b = nextByte();
            } while (b <= ' ');

            while (b > ' ') {
                ret.appendCodePoint(b);
                b = nextByte();
            }

            return ret.toString();
        }

        public byte nextByte() throws IOException {
            if (pointer == bytesRead) {
                bytesRead = din.read(buffer, 0, buffer.length);
                pointer = 0;
            }

            return buffer[pointer++];
        }

        @Override
        public void close() throws IOException {
            if (din == null) {
                return;
            }
            din.close();
        }
    }
}

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