Submission #470874

#	Time	Username	Problem	Language	Result	Execution time	Memory
470874		SansPapyrus683	Cloud Computing (CEOI18_clo)	Java	0 / 100	458 ms	262148 KiB

clo

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;

public class clo {
    public static void main(String[] args) throws IOException {
        BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
        int compNum = Integer.parseInt(read.readLine());
        int[][] computers = new int[compNum][];
        int maxComputers = 0;
        for (int c = 0; c < compNum; c++) {
            // core number, clock rate, and price
            computers[c] = Arrays.stream(read.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            maxComputers += computers[c][0];
        }
        int orderNum = Integer.parseInt(read.readLine());
        int[][] orders = new int[orderNum][];
        for (int c = 0; c < orderNum; c++) {
            // number ordered, min clock rate, and price
            orders[c] = Arrays.stream(read.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }

        // group both the computers and orders into a single transaction array
        int[][] possTransactions = new int[compNum + orderNum][];
        for (int t = 0; t < possTransactions.length; t++) {
            int[] trans;
            if (t < compNum) {
                trans = computers[t];
                if (trans[2] <= 0) {
                    throw new IllegalArgumentException("the price of a computer has to be positive");
                }
                trans[2] = -trans[2];
            } else {
                trans = orders[t - compNum];
                if (trans[2] <= 0) {
                    throw new IllegalArgumentException("the budget of a consumer has to be positive");
                }
            }
            possTransactions[t] = trans;
        }
        // if we sort like this, then the entire clock rate issue goes away as long as we process them in order
        Arrays.sort(possTransactions, Comparator.comparingInt(t -> -t[1]));

        long[][] maxProfits = new long[possTransactions.length + 1][maxComputers + 1];
        Arrays.fill(maxProfits[0], Long.MIN_VALUE);
        maxProfits[0][0] = 0;
        for (int t = 1; t <= possTransactions.length; t++) {
            int[] trans = possTransactions[t - 1];
            maxProfits[t] = maxProfits[t - 1].clone();
            if (trans[2] < 0) {  // we buy some computers
                for (int c = 1; c <= maxComputers; c++) {
                    if (trans[0] <= c && maxProfits[t - 1][c - trans[0]] != Long.MIN_VALUE) {
                        maxProfits[t][c] = Math.max(maxProfits[t - 1][c], maxProfits[t - 1][c - trans[0]] + trans[2]);
                    }
                }
            } else {  // we sell some computers (cores, really, but it doesn't matter)
                for (int c = 1; c <= maxComputers; c++) {
                    if (c + trans[0] <= maxComputers && maxProfits[t - 1][c + trans[0]] != Long.MIN_VALUE) {
                        maxProfits[t][c] = Math.max(maxProfits[t - 1][c], maxProfits[t - 1][c + trans[0]] + trans[2]);
                    }
                }
            }
//            System.out.println(Arrays.toString(maxProfits[t]));
        }
        System.out.println(Arrays.stream(maxProfits[possTransactions.length]).max().getAsLong());
    }
}

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