Untitled

#include<iostream>
using namespace std;
int M,N;
int W[16];
int ans;
int Sum;
void backtrack(int k)
{
	if(Sum > M) {
		return;
	}
	if(k== N){
		if(Sum > ans ){ ans = Sum;}
		return ;
	}
	for(int i=0; i<2; i++){
		if(i==0){
			backtrack(k+1);
		}
		else {
			Sum += W[k];
            backtrack(k+1);
			Sum -= W[k];
		}
	}
}

int main()
{
	int t;
	cin >> t;
	for(int tc= 1; tc <=t; tc ++)
	{
		cin >> M >> N;
		for(int i=0 ; i <N; i++)
		{
			cin >> W[i];
		}
		ans =-1;
		Sum =0;
		backtrack(0);
		cout << "#" << tc << " " << ans<< endl;
	}
	return 0;
}
/////////////////////////////////////////////////
#include<iostream>
using namespace std;
int M,N;
int a[8][8];
int arr[8];
int ans;
bool safe(int r,int c){
	for(int i=0;i<r;i++){
		if(arr[i]==c)return false;
		if(i-arr[i]==r-c)return false;
		if(arr[i]+i==r+c)return false;
	}
	return true;
}
void backtrack(int k)
{
	if(k== 8){
		int sum=0;
		for(int i=0;i<8;i++){
			sum += a[i][arr[i]];
		}
		if(sum>ans)
			ans=sum;
		return;
	}
	for(int i=0; i<8; i++){
		if(safe(k,i)){
			arr[k]=i;
			backtrack(k+1);
		}
	}
}

int main()
{
	//freopen("Text.txt","r",stdin);
	int t;
	cin >> t;
	for(int tc= 1; tc <=t; tc ++)
	{
		int n;
		cin>>n;
		cout << "Case #" << tc<<endl;
		for(int u=0;u<n;u++){
			for(int i=0 ; i <8; i++)
			{
				for(int j=0 ; j <8; j++)
				{
					cin >> a[i][j];
				}
			}
			ans =0;
			backtrack(0);
			cout << ans<< endl;
		}
	}
	return 0;
}
///////////////////////////////////////////////////////
#include<iostream>
using namespace std;
char M[4][4];
int N;
int ans =0;
bool check(int r,int c)
{
	if(M[r][c] == 'X') { return false;}
	for(int i=c-1; i>=0; i--)
	{
		if(M[r][i] == 'C') {return false;}
		if(M[r][i] == 'X') {break;}
	}
	for(int i=r-1; i>=0; i--)
	{
		if(M[i][c] == 'C') {return false;}
		if(M[i][c] == 'X') {break;}
	}
	return true;
}
void backtrack(int k)
{
	if(k == N*N) {
		int count_ =0;
		for(int i=0; i<N; i++)
		{
			for(int j=0; j< N; j++)
			{
				if(M[i][j] == 'C') { count_ ++;}
			}
		}
		if(count_ > ans ) { ans = count_;}
		return ;
	}
	if(check(k/N,k%N))
	{
		for(int i=0; i<2; i++)
		{
         if(i==0) backtrack(k+1);
		 else{
			 M[k/N][k%N] = 'C';
			 backtrack(k+1);
			 M[k/N][k%N] = '.';
		 }
		}
	}
	else backtrack(k+1);


}
int main()
{
	int t;
	cin >> t;
	for(int stt=1; stt <=t; stt ++)
	{
		cin >> N;
		for(int i=0; i<N; i++)
		{
			for(int j=0; j<N; j++)
			{
				cin >> M[i][j];
			}
		}
		///////////////////
		backtrack(0);
		cout << "Case #" << stt << endl << ans << endl;
		ans =0;
	}
}