1099

DP+bitmask

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <sstream>
#include <string>
#include <cstring>
//#include <fstream>
#include <cmath>

using namespace std;

int sizes[16];
int n;
int row,col;
int sum[32780];//1<<n-1=state
int dp[105][32780];//[width or height][state]

int _min(int a,int b)
{
	if(a<b)
	return a;
	return b;
}
//karnighan's bit count algorithm
int check(int x)
{
	int res=0;
	for(res=0;x>0;res++)
	{
		x=x&(x-1);
	}
	return res;
}
int DP(int len,int states)
{
	if(check(states)==1)
	{
		return dp[len][states]=1;
	}
	if(dp[len][states]!=-1)
		return dp[len][states];
	int ans=0,width;
	width = sum[states]/len;
	for(int i=states&(states-1);i>0;i=(i-1)&states)
	{
		int rest = states-i;//= states^i;
		if(sum[i]%len==0 && sum[rest]%len==0)
		{
			ans = DP( _min( len, sum[i]/len ) , i) + DP( _min( len, sum[rest]/len ) , rest);
			if(ans==2)
			return dp[len][states]=1;
		}
		if(sum[i]%width==0 && sum[rest]%width==0)
		{
			ans = DP( _min( width, sum[i]/width ), i) + DP( _min( width, sum[rest]/width ), rest);//states^i == is the state indicates who are not deliverd at state i
			if(ans==2)
			return dp[len][states]=1;
		}
	}
	return dp[len][states]=0;
}

int main()
{
	int tmp,total;
	int kase=1;
	//ofstream out;
	//out.open("my_out.txt");
	while(scanf("%d",&n),n)
	{
		scanf("%d%d",&row,&col);
		total=0;
		for(int i=0;i<n;i++)
		{
			scanf("%d",&sizes[i]);
			total+=sizes[i];
		}
		for(int i=0;i<105;i++)
		{
			for(int j=0;j<32780;j++)
				dp[i][j] = -1;
		}
		for(int i=0;i<(1<<n);i++)
		{
			total = 0;
			for(int j=0;j<n;j++)
			{
				tmp = 1<<j;
				if(i & tmp)
				total += sizes[j];
			}
			sum[i]=total;
		}
		if(sum[(1<<n)-1]!=row*col)
		{
			printf("Case %d: No\n",kase);
			//out<<"Case "<<kase<<": No\n";
			kase+=1;
			continue;
		}
		int f = DP(_min(row,col),(1<<n)-1);//final row and where all the chocklets are accumulated
		if(f==1)
		{
			printf("Case %d: Yes\n",kase);
			kase+=1;
		}
		else
		{
			//out<<"Case "<<kase<<": No\n";
			printf("Case %d: No\n",kase);
			kase+=1;
		}
	}
	//out.close();
	return 0;
}