Submission #468400

#	Time	Username	Problem	Language	Result	Execution time	Memory
468400		rainliofficial	Cloud Computing (CEOI18_clo)	Java	100 / 100	2921 ms	14208 KiB

clo

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

public class clo {
    static int n, m;
    static Item[] arr;
    static int[][] computer, work;
    static long[] dp, pdp;
    public static void main(String[] args) throws IOException{
        BufferedReader file = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader file = new BufferedReader(new FileReader("file.in"));
        //PrintWriter outfile = new PrintWriter (new BufferedWriter(new FileWriter("clo.out")));
        n = Integer.parseInt(file.readLine());
        computer = new int[n][3];
        int sumCores = 0;
        for (int i=0; i<n; i++){
            StringTokenizer st = new StringTokenizer(file.readLine());
            int c = Integer.parseInt(st.nextToken());
            int f = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            computer[i] = new int[] {c, f, e};
        }
        m = Integer.parseInt(file.readLine());
        arr = new Item[n+m];
        work = new int[m][3];
        for (int i=0; i<m; i++){
            StringTokenizer st = new StringTokenizer(file.readLine());
            int c = Integer.parseInt(st.nextToken());
            int f = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            work[i] = new int[] {c, f, e};
            arr[n+i] = new Item(c, f, e, 1); // Set order cores to negative, so we just need to sum all item cores to positive
        }
        for (int i=0; i<n; i++){
            arr[i] = new Item(computer[i][0], computer[i][1], computer[i][2], 0); // Set ernings to negative, so we only take the profit
            sumCores += computer[i][0];
        }
        Arrays.sort(arr);
        dp = new long[sumCores+1];
        pdp = new long[sumCores+1];
        Arrays.fill(dp, (long)-2e17); 
        Arrays.fill(pdp, (long)-2e17); 
        pdp[0] = 0;
        for (int i=1; i<=n+m; i++){
            for (int j=0; j<=sumCores; j++){
                dp[j] = pdp[j];
                if (arr[i-1].t == 0){
                    if (j - arr[i-1].c >= 0){
                        dp[j] = Math.max(dp[j], pdp[j - arr[i-1].c] - arr[i-1].earn);
                    }
                }else{
                    if (j + arr[i-1].c <= sumCores){
                        dp[j] = Math.max(dp[j], pdp[j + arr[i-1].c] + arr[i-1].earn);
                    }
                }
            }
            for (int j=0; j<=sumCores; j++){
                pdp[j] = dp[j];
                dp[j] = (long)-2e17;
            }
        }
        long ans = 0;
        for (int i=0; i<=sumCores; i++){
            ans = Math.max(ans, pdp[i]);
        }
        System.out.println(ans);
    }
    static class Item implements Comparable<Item>{
        int c, f, earn, t;
        public Item(int c, int f, int earn, int t){
            this.c = c;
            this.f = f;
            this.earn = earn;
            this.t = t;
        }
        public int compareTo(Item o){
            if (o.f == this.f){
                if (this.t == o.t){
                    return 0;
                }
                if (this.t == 0){
                    return -1;
                }else{
                    return 1;
                }
            }
            return Integer.compare(o.f, this.f);
        }
    }
}

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