Submission #896187

#	Time	Username	Problem	Language	Result	Execution time	Memory
896187		sushikid	Cloud Computing (CEOI18_clo)	Java	36 / 100	355 ms	262144 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[][] dp = new long[n + m + 1][max_Comp + 1]; //number of transaction, the number of cores
        for (int i = 0; i <= n + m; i++) {
            Arrays.fill(dp[i], Long.MIN_VALUE);
        }
        dp[0][0] = 0;
        for (int i = 1; i <= n + m; i++) {
            for (int j = 0; j <= max_Comp; j++) {
                dp[i][j] = dp[i - 1][j];
                int prev_Cores = j - possible.get(i - 1)[0];
                if(0 <= prev_Cores && prev_Cores <= max_Comp && dp[i - 1][prev_Cores] != Long.MIN_VALUE){
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][prev_Cores] + possible.get(i - 1)[2]); 
                }
            }
        }
        long ans = 0;
        for (int i = 0; i <= max_Comp; i++) {
            ans = Math.max(ans, dp[n + m][i]);
        }
        pw.println(ans);
        pw.close();
    }
}

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