Submission #771323

#	Time	Username	Problem	Language	Result	Execution time	Memory
771323		Oz121	Cloud Computing (CEOI18_clo)	Java	0 / 100	350 ms	262144 KiB

clo

import java.io.*;
import java.util.*;
public class clo {
    public static void main(String[] args) throws IOException {
        BufferedReader scan = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer l1 = new StringTokenizer(scan.readLine());
        int n = Integer.parseInt(l1.nextToken());

        int[][] arr1 = new int[n][3];
        for (int i = 0;i<n;i++) {
            StringTokenizer st = new StringTokenizer(scan.readLine());
            arr1[i][0] = Integer.parseInt(st.nextToken()); arr1[i][1] = Integer.parseInt(st.nextToken()); arr1[i][2] = Integer.parseInt(st.nextToken());
        }

        StringTokenizer l2 = new StringTokenizer(scan.readLine());
        int m = Integer.parseInt(l2.nextToken());

        int[][] arr2 = new int[m][3];
        for (int i = 0;i<m;i++) {
            StringTokenizer st = new StringTokenizer(scan.readLine());
            arr2[i][0] = Integer.parseInt(st.nextToken()); arr2[i][1] = Integer.parseInt(st.nextToken()); arr2[i][2] = Integer.parseInt(st.nextToken());
        }

        int num = n+m;
        int[][] arr = new int[num][3];
        for (int i = 0;i<n;i++) {
            arr[i][0] = arr1[i][0]; arr[i][1] = arr1[i][1]; arr[i][2] = (-1)*arr1[i][2];
        }

        for (int i = 0;i<m;i++) {
            arr[i+n][0] = (-1)*arr2[i][0]; arr[i+n][1] = arr2[i][1]; arr[i+n][2] = arr2[i][2];
        }

        Arrays.sort(arr, (a,b)->b[1]-a[1]);

        //printMat(arr);

        //Now just classic Knapsack
        int maxC = n*50; //Max number of cores possible
        long[][] dp = new long[num][maxC]; //j is the number of cores left, we can never have negative cores
        for (int i = 0;i<num;i++) {
            Arrays.fill(dp[i],Long.MIN_VALUE);
        }

        for (int i = 0;i<num;i++) {
            dp[i][0] = 0;
        }

        if (arr[0][0]>=0)
            dp[0][arr[0][0]] = arr[0][2];

        for (int i = 1;i<num;i++) {
            if (arr[i][0]>=0)
                dp[i][arr[i][0]] = Math.max(dp[i-1][arr[i][0]],arr[i][2]);


            for (int j = 1;j<maxC;j++) {
                if (dp[i][j]==Long.MIN_VALUE) {
                    dp[i][j] = dp[i - 1][j];
                }

                if (maxC>j-arr[i][0]&&j-arr[i][0]>=0) {
                    if (dp[i-1][j-arr[i][0]]!=Long.MIN_VALUE) {

                        if (dp[i-1][j]!=Long.MIN_VALUE)
                            dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - arr[i][0]] + arr[i][2]);
                        else
                            dp[i][j] = dp[i - 1][j - arr[i][0]] + arr[i][2];
                    }
                }

                //System.out.println(dp[i][j]+" "+i+" "+j);
            }
        }

        long ans = 0;
        for (int j = 0;j<maxC;j++) {
            ans = Math.max(ans,dp[num-1][j]);
        }

        System.out.println(ans);
    }

    public static void printMat (int[][] arr) {
        for (int i = 0;i<arr.length;i++) {
            for (int j = 0;j<arr[0].length;j++) {
                System.out.print(arr[i][j]+" ");
            }
            System.out.println();
        }
    }

    public static void printMat (long[][] arr) {
        for (int i = 0;i<arr.length;i++) {
            for (int j = 0;j<arr[0].length;j++) {
                System.out.print(arr[i][j]+" ");
            }
            System.out.println();
        }
    }
}

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