Untitled

//Quang Cao
package adver;

import java.util.Scanner;

public class test {
static int N;
static int[][] QC=new int[4][2];
static int[][] QC_time=new int[4][2];
static int[] checkQC=new int[4];
static int[][] time=new int[52][2];
static int[] timesetup=new int[52];
static int[] point_person=new int[52];
static int min_time=0;
static int max_time=0;
static int ans=0;
static int check,check1;
static int Score() {
	int point=0;
	for(int i=1;i<=N;i++) {
		for(int j=1;j<=3;j++) {
			if(time[i][0]<=QC_time[j][0] && time[i][1]>=QC_time[j][1]) {
				if(QC[j][1]>point_person[i]) {
					point_person[i]=QC[j][1];
				}
			}
		}
		point+=point_person[i];
		point_person[i]=0;
	}
	return point;
}

static void backtrack(int step,int k) {
	if(step==3) {
		if(Score()>ans) {
			ans=Score();
		}
		return;
	}
	if(checkQC[k]==0) {
		checkQC[k]=1;
		for(int i=min_time;i<=max_time-QC[k][0];i++) {
			check=0;
			check1=0;
			for(int j=i;j<i+QC[k][0];j++) {
				if(timesetup[j]!=0) {
					check=1;
					break;
				}
			}
			if(i==max_time-QC[k][0] && check==1) check1=1;
			if(check==1) continue;
			for(int j=i;j<i+QC[k][0];j++ ) {
				timesetup[j]=k;
			}
			QC_time[k][0]=i;
			QC_time[k][1]=i+QC[k][0];
			backtrack(step+1, k+1);
			for(int j=i;j<i+QC[k][0];j++ ) {
				timesetup[j]=0;
			}
			QC_time[k][0]=0;
			QC_time[k][1]=0;
			
		}
		if(check1==1) {
			backtrack(step+1, k+1);
		}
		checkQC[k]=0;
	}
	
}
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();
		for(int i=1;i<=3;i++) {
			QC[i][0]=sc.nextInt();
		}
		for(int i=1;i<=3;i++) {
			QC[i][1]=sc.nextInt();
		}
		max_time=0;
		min_time=10000;
		for(int i=1;i<=N;i++) {
			time[i][0]=sc.nextInt();
			int tmp=sc.nextInt();
			time[i][1]=time[i][0]+tmp;
			if(time[i][1]>max_time) max_time=time[i][1];
			if(time[i][0]<min_time) min_time=time[i][0];
		}
		ans=0;
		backtrack(0, 1);
		System.out.println("Case #"+tc);
		System.out.println(ans);
	}
}
}

//Thong tri khu vuc
package ThongTriKhuVuc;

import java.util.Scanner;
class MyQueue{
	private int size;
	private int[] array;
	private int in;
	private int out;
	public MyQueue(int size) {
		this.size = size;
		array=new int[size];
		in=-1;
		out=-1;
	}
	public void push(int x) {
		in++;
		array[in]=x;
	}
	public int pop() {
		out++;
		return array[out];
	}
	public boolean isEmpty() {
		if(in==out) {
			return true;
		}
		return false;
	}
	public void reset() {
		in=out=-1;
	}
	
}
public class test {
static int N;
static int[][] map=new int[100][100];
static int[][] vs=new int[100][100];
static int[] soLan=new int[6];
static MyQueue queueX=new MyQueue(10000);
static MyQueue queueY=new MyQueue(10000);
static MyQueue queueX1=new MyQueue(10000);
static MyQueue queueY1=new MyQueue(10000);
static int[] dx= {0,-1,0,1};
static int[] dy= {-1,0,1,0};
static int count=0;
//reset solan
static void RSsolan() {
	for(int i=0;i<=5;i++) {
		soLan[i]=0;
	}
}
//reset visit
static void RSvisit() {
	for(int i=0;i<N;i++) {
		for(int j=0;j<N;j++) {
			vs[i][j]=0;
		}
	}
}
//BFS
static void BFS_0(int x,int y) {
	queueX.reset();
	queueY.reset();
	queueX.push(x);
	queueY.push(y);
	vs[x][y]=count;
	while(!queueX.isEmpty()) {
		int xx=queueX.pop();
		int yy=queueY.pop();
		for(int i=0;i<4;i++) {
			int r=xx+dx[i];
			int c=yy+dy[i];
			if(r<0 || r>=N || c<0 || c>=N ) continue;
			if(map[r][c]==0 && vs[r][c]==0) {
				queueX.push(r);
				queueY.push(c);
				vs[r][c]=count;
			}
			else if(map[r][c]!=0 && vs[r][c]==0) {
				soLan[map[r][c]]++;
				BFS_1(r,c);
			}
		}
	}
}
//BFS_1
static void BFS_1(int x,int y) {
	queueX1.reset();
	queueY1.reset();
	queueX1.push(x);
	queueY1.push(y);
	vs[x][y]=1;
	while(!queueX1.isEmpty()) {
		int xx=queueX1.pop();
		int yy=queueY1.pop();
		for(int i=0;i<4;i++) {
			int r=xx+dx[i];
			int c=yy+dy[i];
			if(r<0 || r>=N || c<0 || c>=N ) continue;
			if(map[r][c]==map[xx][yy]&& vs[r][c]==0) {
				queueX1.push(r);
				queueY1.push(c);
				vs[r][c]=1;
				soLan[map[r][c]]++;
			}
		}
	}
}
//BFS Gan
static void BFS_Gan(int x,int y,int val) {
	queueX1.reset();
	queueY1.reset();
	queueX1.push(x);
	queueY1.push(y);
	map[x][y]=val;
	while(!queueX1.isEmpty()) {
		int xx=queueX1.pop();
		int yy=queueY1.pop();
		for(int i=0;i<4;i++) {
			int r=xx+dx[i];
			int c=yy+dy[i];
			if(r<0 || r>=N || c<0 || c>=N ) continue;
			if(map[r][c]==0 && vs[r][c]==count) {
				queueX1.push(r);
				queueY1.push(c);
				map[r][c]=val;
			}
		}
	}
}
//main
public static void main(String[] args) {
	Scanner sc=new Scanner(System.in);
	int T=sc.nextInt();
	for(int tc=0;tc<T;tc++) {
		N=sc.nextInt();
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				map[i][j]=sc.nextInt();
			}
		}
		RSvisit();
		count=2;
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				if(map[i][j]==0 && vs[i][j]==0) {
					RSsolan();
					BFS_0(i, j);
					for(int m=0;m<N;m++) {
						for(int n=0;n<N;n++) {
							if(map[m][n]!=0 && vs[m][n]==1) {
								vs[m][n]=0;
							}
						}
					}
					int max=0;
					int tmp=0;
					for(int m=0;m<=5;m++) {
						if(soLan[m]>=max) {
							max=soLan[m];
							tmp=m;
						}
					}
					BFS_Gan(i, j, tmp);
					count++;
				}
			}
		}
		RSvisit();
		int ans=0;
		for(int m=0;m<N;m++) {
			for(int n=0;n<N;n++) {
				if(vs[m][n]==0) {
					ans++;
					BFS_1(m, n);
				}
			}
		}
		System.out.println("Case #"+(tc+1));
		System.out.println(ans);
	}
}
}