제출 #471007

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
471007		SansPapyrus683	Cloud Computing (CEOI18_clo)	Java	54 / 100	3042 ms	20260 KiB

clo

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

/**
 * https://oj.uz/problem/view/CEOI18_clo
 * 4
 * 4 2200 700
 * 2 1800 10
 * 20 2550 9999
 * 4 2000 750
 * 3
 * 1 1500 300
 * 6 1900 1500
 * 3 2400 4550 should output 350
 * (algorithm is right, it's just that java is way too slow)
 */
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][3];
        int maxComputers = 0;
        for (int c = 0; c < compNum; c++) {
            // core number, clock rate, and price
            StringTokenizer comp = new StringTokenizer(read.readLine());
            computers[c][0] = Integer.parseInt(comp.nextToken());
            computers[c][1] = Integer.parseInt(comp.nextToken());
            computers[c][2] = Integer.parseInt(comp.nextToken());
            maxComputers += computers[c][0];
        }
        int orderNum = Integer.parseInt(read.readLine());
        int[][] orders = new int[orderNum][3];
        for (int c = 0; c < orderNum; c++) {
            // number ordered, min clock rate, and price
            StringTokenizer order = new StringTokenizer(read.readLine());
            orders[c][0] = Integer.parseInt(order.nextToken());
            orders[c][1] = Integer.parseInt(order.nextToken());
            orders[c][2] = Integer.parseInt(order.nextToken());
        }

        // 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];
                // we gain a negative amount of money!
                trans[2] = -trans[2];
            } else {
                trans = orders[t - compNum];
                // we gain a negative amount of cores lol
                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 = 0; 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: 18 / 18
• Subtask 2: 18 / 18
• Subtask 3: 18 / 18
• Subtask 4: 0 / 18
• Subtask 5: 0 / 18
• Subtask 6: 0 / 10