记录编号	264034	评测结果	A
题目名称	[POJ 1014] 大理石分割	最终得分	100
用户昵称	农场主	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2016-05-27 09:14:48	内存使用	0.44 MiB

#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
bool d[20000*7]={0};
vector<int> t;
int a[7]={0};
int n=6,mid=0;
void work(){
	memset(d,0,sizeof(d));
	t.clear();
	mid=0;
	for (int i=1;i<=n;i++){
		mid+=a[i]*i;
		for (int j=0;a[i];j++){
			if (a[i]>=(1<<j)){
				a[i]-=(1<<j);
				t.push_back(i*(1<<j));
			}
			else {
				t.push_back(i*a[i]);
				a[i]=0;
			}
		}
	}
	int tot=0;
	if (mid%2==1) {
		printf("Can't be divided.\n");
		return;
	}
	mid/=2;
	d[0]=1;
	for (int i=0;i<t.size();i++){
		for (int j=tot;j>=0;j--){
			if (d[j]==1){
				d[j+t[i]]=1;
			}
		}
		if (tot+t[i]<=mid) tot+=t[i];
		if (d[mid]==1) break;
	}
	if (d[mid]==1) printf("Can be divided.\n");
	else printf("Can't be divided.\n");
}
int main(){
	freopen("dividestone.in","r",stdin);
	freopen("dividestone.out","w",stdout);
	for (int k=1;;k++){
		for (int i=1;i<=n;i++){
			scanf("%d",&a[i]);
		}
		if (!a[1]&&!a[2]&&!a[3]&&!a[4]&&!a[5]&&!a[6]) break;
		printf("\nCollection #%d:\n",k);
		work();
	}
	return 0;
}