Submission #523638

#	Time	Username	Problem	Language	Result	Execution time	Memory
523638		Longgggggggg	Cloud Computing (CEOI18_clo)	Java	100 / 100	2939 ms	15184 KiB

clo

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

public class clo {
    static long INF = (long) 1e18;

    public static void main(String[] args) {
        FastIO io = new FastIO();
        int n = io.nextInt();
        Item[] items = new Item[n];
        for (int i = 0; i < n; i++) items[i] = new Item(io.nextInt(), io.nextInt(), -io.nextInt());
        int m = io.nextInt();
        items = Arrays.copyOf(items, m + n);
        for (int i = 0; i < m; i++) items[n + i] = new Item(-io.nextInt(), io.nextInt(), io.nextInt());
        Arrays.sort(items, (a, b) -> a.f == b.f ? a.p - b.p : b.f - a.f);
        long[][] dp = new long[2][50 * n + 1];
        for (long[] row : dp) Arrays.fill(row, -INF);
        dp[0][0] = 0;
        for (int i = 1; i <= n + m; i++) {
            for (int j = 0; j <= 50 * n; j++) {
                dp[i % 2][j] = dp[(i - 1) % 2][j];
                if (j >= items[i - 1].c && j - items[i - 1].c <= 50 * n)
                    dp[i % 2][j] = Math.max(dp[(i - 1) % 2][j - items[i - 1].c] + items[i - 1].p, dp[i % 2][j]);
            }
        }
        long max = 0;
        for (int j = 0; j <= 50 * n; j++) max = Math.max(dp[(m + n) % 2][j], max);
        io.println(max);
        io.close();
    }

    static class Item {
        int c, f, p;

        public Item(int c, int f, int p) {
            this.c = c;
            this.f = f;
            this.p = p;
        }
    }

    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());
        }
    }

}

• Subtask 1: 18 / 18
• Subtask 2: 18 / 18
• Subtask 3: 18 / 18
• Subtask 4: 18 / 18
• Subtask 5: 18 / 18
• Subtask 6: 10 / 10