记录编号 264034 评测结果 A
题目名称 [POJ 1014] 大理石分割 最终得分 100
用户昵称 Gravatar农场主 是否通过 通过
代码语言 C++ 运行时间 0.002 s
提交时间 2016-05-27 09:14:48 内存使用 0.44 MiB
显示代码纯文本
  1. #include<cstdio>
  2. #include<vector>
  3. #include<algorithm>
  4. #include<cstring>
  5. using namespace std;
  6. bool d[20000*7]={0};
  7. vector<int> t;
  8. int a[7]={0};
  9. int n=6,mid=0;
  10. void work(){
  11. memset(d,0,sizeof(d));
  12. t.clear();
  13. mid=0;
  14. for (int i=1;i<=n;i++){
  15. mid+=a[i]*i;
  16. for (int j=0;a[i];j++){
  17. if (a[i]>=(1<<j)){
  18. a[i]-=(1<<j);
  19. t.push_back(i*(1<<j));
  20. }
  21. else {
  22. t.push_back(i*a[i]);
  23. a[i]=0;
  24. }
  25. }
  26. }
  27. int tot=0;
  28. if (mid%2==1) {
  29. printf("Can't be divided.\n");
  30. return;
  31. }
  32. mid/=2;
  33. d[0]=1;
  34. for (int i=0;i<t.size();i++){
  35. for (int j=tot;j>=0;j--){
  36. if (d[j]==1){
  37. d[j+t[i]]=1;
  38. }
  39. }
  40. if (tot+t[i]<=mid) tot+=t[i];
  41. if (d[mid]==1) break;
  42. }
  43. if (d[mid]==1) printf("Can be divided.\n");
  44. else printf("Can't be divided.\n");
  45. }
  46. int main(){
  47. freopen("dividestone.in","r",stdin);
  48. freopen("dividestone.out","w",stdout);
  49. for (int k=1;;k++){
  50. for (int i=1;i<=n;i++){
  51. scanf("%d",&a[i]);
  52. }
  53. if (!a[1]&&!a[2]&&!a[3]&&!a[4]&&!a[5]&&!a[6]) break;
  54. printf("\nCollection #%d:\n",k);
  55. work();
  56. }
  57. return 0;
  58. }