hugo_xeplichquangcao

 avatar
duyvan
plain_text
2 years ago
1.8 kB
4
Indexable
import java.util.Scanner;

/*
As the name of the class should be Solution, using Solution.java as the filename is recommended.
In any case, you can execute your program by running 'java Solution' command.
*/
class Solution
{
	static int N, ans;
	static int[] lengthAd, pointAd, arrive, duration, beginAd, endAd, pointAt;
	static boolean[] visited;

	public static void main(String[] args) {


		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			lengthAd = new int[3];
			pointAd = new int[3];
			for (int i = 0; i < 3; i++) {
				lengthAd[i] = sc.nextInt();
			}
			for (int i = 0; i < 3; i++) {
				pointAd[i] = sc.nextInt();
			}
			arrive = new int[N];
			duration = new int[N];
			for (int i = 0; i < N; i++) {
				arrive[i] = sc.nextInt();
				duration[i] = sc.nextInt();
			}
			visited = new boolean[3];
			beginAd = new int[3];
			endAd = new int[3];
			pointAt = new int[3];
			ans = 0;
			backTrack(1, 0);
			System.out.println("Case #" + tc + "\n" + ans);
		}
	}

	private static void backTrack(int time, int k) {
		if (time > 50 || k == 3) {
			calcu(k);
			return;
		}
		backTrack(time + 1, k);
		for (int i = 0; i < 3; i++) {
			if (!visited[i]) {
				visited[i] = true;
				beginAd[k] = time;
				endAd[k] = time + lengthAd[i];
				pointAt[k] = pointAd[i];
				backTrack(endAd[k], k + 1);
				visited[i] = false;
			}
		}
	}

	private static void calcu(int k) {
		int sum = 0;
		for (int i = 0; i < N; i++) {
			int point = 0;
			for (int j = 0; j < k; j++) {
				if (arrive[i] <= beginAd[j]
						&& arrive[i] + duration[i] >= endAd[j]) {
					if (pointAt[j] > point) {
						point = pointAt[j];
					}
				}
			}
			sum += point;
		}
		if (sum > ans) {
			ans = sum;
		}

	}
}
Editor is loading...
Leave a Comment