Untitled
plain_text
a month ago
2.2 kB
1
Indexable
Never
package hugo_sx_quang_cao; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class Solution { static int n, min, max, res; static int[][] hvi = { { 0, 1, 2 }, { 0, 2, 1 }, { 1, 0, 2 }, { 1, 2, 0 }, { 2, 0, 1 }, { 2, 1, 0 } }; static int[] Arrival, Duration, point, Length = new int[3], Point = new int[3], start = new int[3], show; public static int p(int hv) { point = new int[n+1]; int sum = 0; for (int i = 1; i <= n; i++) { for(int j = 0; j < 3; j++){ if(Arrival[i] <= start[j] && Arrival[i] + Duration[i] >= start[j] + Length[hvi[hv][j]]){ if(point[i] < Point[hvi[hv][j]]){ point[i] = Point[hvi[hv][j]]; } } } sum += point[i]; } return sum; } static void backTrack(int k, int hv) { if (k == 3) { res = Math.max(res, p(hv)); return; } int st = min; if(k != 0) st = start[k-1] + Length[hvi[hv][k-1]]; for(int i = st; i <= max; i++){ start[k] = i; backTrack(k + 1, hv); start[k] = 0; } } public static void main(String[] args) { try { System.setIn(new FileInputStream("input.txt")); } catch (FileNotFoundException e) { // TODO Auto-generated catch block e.printStackTrace(); } Scanner scanner = new Scanner(System.in); int test = scanner.nextInt(); for (int t = 1; t <= test; t++) { n = scanner.nextInt(); for (int i = 0; i < 3; i++) { Length[i] = scanner.nextInt(); } for (int i = 0; i < 3; i++) { Point[i] = scanner.nextInt(); } Arrival = new int[n + 1]; Duration = new int[n + 1]; min = Integer.MAX_VALUE; max = 0; for (int i = 1; i <= n; i++) { Arrival[i] = scanner.nextInt(); Duration[i] = scanner.nextInt(); if (Arrival[i] + Duration[i] > max) { max = Arrival[i] + Duration[i]; } if (Arrival[i] < min) { min = Arrival[i]; } } res = 0; for (int i = 0; i < 6; i++) { // System.out.println(); point = new int[n + 1]; show = new int[max]; backTrack(0, i); } System.out.println("Case #" + t + "\n" + res); } scanner.close(); } }