Submission #470876

#	Time	Username	Problem	Language	Result	Execution time	Memory
470876		SansPapyrus683	Cloud Computing (CEOI18_clo)	Java	0 / 100	3034 ms	20700 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");
                }
                trans[0] = -trans[0];
            }
            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[maxComputers + 1];
        Arrays.fill(maxProfits, Long.MIN_VALUE);
        maxProfits[0] = 0;
        for (int[] t : possTransactions) {
            long[] newMax = maxProfits.clone();
            for (int c = 1; c <= maxComputers; c++) {
                int prevComp = c - t[0];
                if (0 <= prevComp && prevComp <= maxComputers && maxProfits[prevComp] != Long.MIN_VALUE) {
                    newMax[c] = Math.max(newMax[c], maxProfits[prevComp] + t[2]);
                }
            }
            maxProfits = newMax;
        }
        System.out.println(Arrays.stream(maxProfits).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