hugo_xeplichquangcao
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