제출 #771322

#제출 시각아이디문제언어결과실행 시간메모리
771322Oz121Cloud Computing (CEOI18_clo)Java
0 / 100
337 ms206524 KiB
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],-1); } 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]==-1) { 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]]!=-1) { if (dp[i-1][j]!=-1) 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(); } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...