Submission #771413

#	Time	Username	Problem	Language	Result	Execution time	Memory
771413		Oz121	Cloud Computing (CEOI18_clo)	Java	100 / 100	1929 ms	15016 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] ? b[1]-a[1] : a[2]-b[2]);

        //printMat(arr);

        //Now just classic Knapsack
        int maxC = n*50+1; //Max number of cores possible

        long[] dp1 = new long[maxC]; long[] dp2 = new long[maxC];
        Arrays.fill(dp1,Long.MIN_VALUE);
        Arrays.fill(dp2,Long.MIN_VALUE);

        dp1[0] = 0; dp2[0] = 0;

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

        for (int i = 1;i<num;i++) {
            if (arr[i][0]>=0) {
                dp2[arr[i][0]] = arr[i][2];
            }

            for (int j = 0;j<maxC;j++) {
                dp2[j] = Math.max(dp2[j],dp1[j]);

                if (maxC>j-arr[i][0]&&j-arr[i][0]>=0) {
                    if (dp1[j-arr[i][0]]!=Long.MIN_VALUE) {
                        dp2[j] = Math.max(dp2[j], dp1[j - arr[i][0]] + arr[i][2]);
                    }
                }
            }

            for (int j = 0;j<maxC;j++) {
                dp1[j] = dp2[j];

                if (j==0)
                    dp2[0] = 0;
                else
                    dp2[j] = Long.MIN_VALUE;
            }
        }

        long ans = 0;
        for (int j = 0;j<maxC;j++) {
            ans = Math.max(ans,dp1[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: 18 / 18
• Subtask 2: 18 / 18
• Subtask 3: 18 / 18
• Subtask 4: 18 / 18
• Subtask 5: 18 / 18
• Subtask 6: 10 / 10