Advertisement
bibaboba12345

Untitled

May 25th, 2022
107
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.65 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <set>
  4. #include <vector>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. const int N = 505;
  10. bool poss[505][250001];
  11. vector<int> answ, pos, pos2;
  12. int a[N], n, sumAll = 0;
  13. int dp[N * N];
  14.  
  15.  
  16. int main()
  17. {
  18. #ifdef _DEBUG
  19. freopen("input.txt", "r", stdin);
  20. #else
  21. std::ios::sync_with_stdio(false);
  22. cin.tie(0);
  23. #endif
  24. cin >> n;
  25. for (int i = 0; i < n; i++) {
  26. cin >> a[i];
  27. sumAll += a[i];
  28. }
  29. sort(a, a + n);
  30. //reverse(a, a + n);
  31. for (int ign = 0; ign < n; ign++) {
  32. for (int i = 0; i <= 500 * 500; i++) {
  33. dp[i] = 1e9;
  34. }
  35. for (int i = 0; i < n; i++) {
  36. if (i != ign) {
  37. dp[a[i]] = min(i, dp[a[i]]);
  38. }
  39. }
  40. for (int sm = 0; sm <= 500 * 500; sm++) {
  41. if (dp[sm] == 1e9) {
  42. continue;
  43. }
  44. poss[ign][sm] = 1;
  45. int nextInd = dp[sm] + 1;
  46. if (nextInd == ign) {
  47. nextInd++;
  48. }
  49. dp[sm + a[nextInd]] = min(dp[sm + a[nextInd]], nextInd); // в конец
  50. dp[sm + a[nextInd] - a[dp[sm]]] = min(dp[sm + a[nextInd] - a[dp[sm]]], nextInd); // вместо
  51. }
  52. poss[ign][0] = 1;
  53. }
  54.  
  55. if (sumAll % 2) { // вообще не разбить когда снимает
  56. cout << "0";
  57. return 0;
  58. }
  59. if (!poss[0][(sumAll) / 2 - a[0]]) { // тоже не разбить пока снимает
  60. cout << "0";
  61. return 0;
  62. }
  63. for (int str = 1; str <= sumAll; str++) {
  64. bool fl = 1;
  65. for (int i = 0; i < n; i++) {
  66.  
  67. if (!poss[i][(sumAll + str - a[i]) / 2 - str] || (sumAll + str - a[i]) % 2) {
  68. fl = 0;
  69. }
  70. }
  71. if (fl) {
  72. answ.push_back(str);
  73. }
  74. }
  75. cout << answ.size() << "\n";
  76. for (auto h : answ) {
  77. cout << h << " ";
  78. }
  79. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement