Advertisement
Guest User

Untitled

a guest
Mar 29th, 2015
229
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.71 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <set>
  5. #include <cmath>
  6. #include <map>
  7.  
  8. using namespace std;
  9.  
  10. vector <int> a;
  11.  
  12. int main()
  13. {
  14. // freopen("cakes.in", "r", stdin);
  15. // freopen("cakes.out", "w", stdout);
  16. int n;
  17. cin >> n;
  18. a.resize(n);
  19. for (int i = 0; i < n; i++)
  20. cin >> a[i];
  21. bool dp[301][301]; //dp[i][j] - за i людей набрать сумму j
  22. bool dp2[301][301];
  23. int p[301][301];
  24. for (int q = 0; q <= n; q++)
  25. for (int j = 0; j <= n; j++)
  26. dp[q][j] = false, p[q][j] = -1;
  27. dp[0][0] = true;
  28. for (int i = 0; i < n; i++)
  29. {
  30. for (int q = 0; q <= n; q++)
  31. for (int j = 0; j <= n; j++)
  32. dp2[q][j] = false;
  33. for (int q = 0; q < n; q++)
  34. for (int j = 0; j <= n; j++)
  35. {
  36. if (dp[q][j])
  37. {
  38. if (j + a[i] <= n)
  39. {
  40. dp2[q + 1][j + a[i]] |= dp[q][j];
  41. if (p[q + 1][j + a[i]] == -1)
  42. p[q + 1][j + a[i]] = i;
  43. }
  44. else break;
  45. }
  46. }
  47. for (int q = 0; q <= n; q++)
  48. for (int j = 0; j <= n; j++)
  49. dp[q][j] |= dp2[q][j];
  50. }
  51. int res = -1;
  52. for (int q = 0; q <= n; q++)
  53. if (dp[q][n - q])
  54. {
  55. res = q;
  56. break;
  57. }
  58. if (res == -1)
  59. {
  60. cout << "NO\n";
  61. return 0;
  62. }
  63. else
  64. {
  65. cout << "YES\n";
  66. pair <int, int> cur = make_pair(res, n - res);
  67. vector <int> best;
  68. while (cur.first > 0)
  69. {
  70. int to = p[cur.first][cur.second];
  71. best.push_back(to);
  72. cur.first--;
  73. cur.second = cur.second - a[to];
  74. }
  75. vector <int> result;
  76. result.resize(n);
  77. for (int i = 0; i < n; i++)
  78. result[i] = 0;
  79. for (int i = 0; i < best.size(); i++)
  80. result[best[i]] = 1;
  81. for (int i = 0; i < n; i++)
  82. cout << result[i];
  83. }
  84. return 0;
  85. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement