Untitled

 avatar
unknown
plain_text
a year ago
2.2 kB
13
Indexable
package Bai1;

import java.io.FileInputStream;
import java.util.Scanner;

public class HugoAds {
	static int noV;
	static int[][] ads = new int[3][2];
	static int[][] info = new int[3][2];
	static int[][] vis = new int[51][2];
	static int[] visit = new int[100];
	static int max;
	static int maxleft;
	
	static boolean check(int s, int id){
		for(int i = s; i < s + ads[id][0]; i++){
			if (visit[i] != -1)	return false;
		}
		return true;
	}
	static int checkPoint(){
		int sum = 0;
		for (int i = 0; i < noV; i++){
			int point;
			int maxpoint = 0;
			int a = vis[i][0];
			int d = vis[i][1];
			for (int j = 0; j < 3; j++){
				int a1 = info[j][0];
				int d1 = info[j][1];
				if (a <= a1 && d >= d1){
					point = ads[j][1];
					if (point > maxpoint)	maxpoint = point;
				}
			}
			sum += maxpoint;
		}
		return sum;
	}

	static void backtrack(int id){
		if (id == 3){
			int point = checkPoint();
			if (point > max)	max = point;
			return;
		}
		for(int i = 1; i <= maxleft; i++){
			if (!check(i, id))	continue;
			for (int j = i; j < i + ads[id][0]; j++){
				visit[j] = 1;
			}
			info[id][0] = i;
			info[id][1] = ads[id][0] + i;
			backtrack(id+1);
			for (int j = i; j < i + ads[id][0]; j++){
				visit[j] = -1;
			}
			info[id][0] = 0;
			info[id][1] = 0;
		}
	}
	
	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		System.setIn(new FileInputStream("input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++){
			noV = sc.nextInt();
			for (int i = 0; i < 3; i++){
				ads[i][0] = sc.nextInt();	//length

			}
			for (int i = 0; i < 3; i++){
				ads[i][1] = sc.nextInt();	//point

			}
			maxleft = 0;
			for(int i = 0; i < 100; i++){
				visit[i] = -1;
			}
			for (int i = 0; i < noV; i++){
				int a = sc.nextInt();
				int d = sc.nextInt();
				vis[i][0] = a;
				vis[i][1] = a + d;
				
				if(vis[i][1] > maxleft)	maxleft = vis[i][1];
				//System.out.println(maxleft);
			}
			max = 0;
			backtrack(0);
			System.out.println("Case #" + tc + "\n" + max);
		}
	}

}
Leave a Comment