Submission #486555

#	Time	Username	Problem	Language	Result	Execution time	Memory
486555		john256	Cloud Computing (CEOI18_clo)	Java	72 / 100	3012 ms	28240 KiB

clo

import java.util.*;
import java.io.*;
public class clo {
	public static void main(String[] aaaa) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		//possible transactions
		ArrayList<Transaction> poss_transactions = new ArrayList<>(); 
	
		int max_CPUS = 0; //max # of CPUS
		
		int N = Integer.parseInt(br.readLine()); //# of computers available
		for(int x=0; x<N; x++) {
			Transaction trans = new Transaction();
			StringTokenizer st = new StringTokenizer(br.readLine());
			trans.cores = Integer.parseInt(st.nextToken());
			trans.rate = Integer.parseInt(st.nextToken());
			trans.price = Integer.parseInt(st.nextToken());
			trans.price = -trans.price;
			poss_transactions.add(trans);
			max_CPUS += trans.cores;
		}
	
		int M = Integer.parseInt(br.readLine()); //# of orders from customers
		for(int y=0; y<M; y++) {
			Transaction trans = new Transaction();
			StringTokenizer st = new StringTokenizer(br.readLine());
			trans.cores = Integer.parseInt(st.nextToken());
			trans.rate = Integer.parseInt(st.nextToken());
			trans.price = Integer.parseInt(st.nextToken());;
			trans.cores = -trans.cores;
			poss_transactions.add(trans);
		}
	
		//The clock rate issue goes away if we process the orders in order.
		Collections.sort(poss_transactions,
			  (a, b)-> a.rate != b.rate ? b.rate - a.rate : a.price - b.price);
	
		/*
		 * max_profits[t][c] = the maximum profit we can gain from the first
		 *   t transactions given that we have c cores left
		 */
		long[] max_profits = new long[max_CPUS+1];
		Arrays.fill(max_profits, Long.MIN_VALUE);
		
		max_profits[0] = 0L;
		for(Transaction t : poss_transactions) {
			long[] new_max = new long[max_CPUS+1];
			for(int j=0; j<max_CPUS+1; j++)
				new_max[j] = max_profits[j];
			
			for(int c=0; c<=max_CPUS; c++) {
				int prev_comp = c - t.cores;
				if(0 <= prev_comp && prev_comp <= max_CPUS
						&& max_profits[prev_comp] != Long.MIN_VALUE) {
					new_max[c] = Math.max(new_max[c], max_profits[prev_comp] + t.price);
				}
			}
			max_profits = new_max;
		}
		
		Arrays.sort(max_profits);
		
		System.out.println(max_profits[max_CPUS]);
	}
	
	static class Transaction {
		int cores;
		int rate;
		int price;
	}
}

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