Submission #896188

#	Time	Username	Problem	Language	Result	Execution time	Memory
896188		sushikid	Cloud Computing (CEOI18_clo)	Java	100 / 100	2175 ms	31412 KiB

clo

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

public class clo {
    public static void main(String[] args) throws IOException{
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        ArrayList<int[]> possible = new ArrayList<>();
        int max_Comp = 0;
        int n = Integer.parseInt(r.readLine());
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(r.readLine());
            int c = Integer.parseInt(st.nextToken()); int f = Integer.parseInt(st.nextToken()); int v = Integer.parseInt(st.nextToken());
            max_Comp += c;
            possible.add(new int[]{c, f, -v});
        }
        int m = Integer.parseInt(r.readLine());
        for (int i = 0; i < m; i++) {
            StringTokenizer st = new StringTokenizer(r.readLine());
            int c = Integer.parseInt(st.nextToken()); int f = Integer.parseInt(st.nextToken()); int v = Integer.parseInt(st.nextToken());
            possible.add(new int[]{-c, f, v});
        }
        Collections.sort(possible, (a, b) -> -Integer.compare(a[1], b[1]));
        // Arrays.sort(orders, (a, b) -> -Integer.compare(a[1], b[1]));
        long[] dp1 = new long[max_Comp + 1]; //number of transaction, the number of cores
        long[] dp2 = new long[max_Comp + 1];
        Arrays.fill(dp1, Long.MIN_VALUE); Arrays.fill(dp2, Long.MIN_VALUE);
        dp1[0] = dp2[0] = 0;
        for (int i = 0; i < n + m; i++) {
            for (int j = 0; j <= max_Comp; j++) {
                int prev_Cores = j - possible.get(i)[0];
                if(0 <= prev_Cores && prev_Cores <= max_Comp && dp1[prev_Cores] != Long.MIN_VALUE){
                    dp2[j] = Math.max(dp2[j], dp1[prev_Cores] + possible.get(i)[2]); 
                }
            }
            for (int j = 0; j <= max_Comp; j++) {
                dp1[j] = dp2[j];
            }
        }
        long ans = 0;
        for (int i = 0; i <= max_Comp; i++) {
            ans = Math.max(ans, dp1[i]);
        }
        pw.println(ans);
        pw.close();
    }
}

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