Advertisement
Guest User

Untitled

a guest
Dec 16th, 2017
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.78 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <string>
  6. #include <vector>
  7. #include <stack>
  8. #include <queue>
  9. #include <set>
  10. #include <cstring>
  11. #include <map>
  12. #include <cstdlib>
  13. #include <ctime>
  14. #include <cassert>
  15. #include <bitset>
  16. #define f first
  17. #define s second
  18. #define ll long long
  19. #define ull unsigned long long
  20. #define mp make_pair
  21. #define pb push_back
  22. #define vi vector <int>
  23. #define ld long double
  24. #define pii pair<int, int>
  25. #define y1 sda
  26. using namespace std;
  27. const int N = 502, mod1 = int(1e9) + 7, mod2 = int(1e9) + 9;
  28.  
  29. int n,a[N];
  30.  
  31. int s, sum;
  32.  
  33. int dp[N * N];
  34. int f[N * N];
  35. vi ans;
  36. bool used[N];
  37.  
  38. inline void add(int x){
  39. for(int j = sum; j >= 0; j--){
  40. dp[j + x] += dp[j];
  41. if(dp[j + x] >= mod1) dp[j + x] -= mod1;
  42. }
  43. sum += x;
  44. }
  45.  
  46. inline void del(int x){
  47. sum -= x;
  48. for(int j = 0; j <= sum; j++){
  49. dp[j + x] += (mod1 - dp[j]);
  50. if(dp[j + x] >= mod1) dp[j + x] -= mod1;
  51. }
  52. }
  53.  
  54. int main () {
  55. freopen("bootfall.in","r", stdin);
  56. freopen("bootfall.out","w", stdout);
  57. scanf("%d",&n);
  58. bool odd = 0, even = 0;
  59. for(int i = 1; i <= n; i++){
  60. scanf("%d",&a[i]);
  61. s += a[i];
  62. if(a[i] & 1) odd = 1;
  63. else even = 1;
  64. }
  65. if(odd && even){
  66. printf("0");
  67. return 0;
  68. }
  69. dp[0] = 1;
  70. for(int i = 1; i <= n; i++){
  71. add(a[i]);
  72. }
  73. if((s & 1) || !dp[s>>1]){
  74. printf("0");
  75. return 0;
  76. }
  77. for(int i = 1; i <= n; i++){
  78. if(used[a[i]]) continue;
  79. used[a[i]] = 1;
  80. del(a[i]);
  81. for(int j = 1; j <= s; j++){
  82. int cur = s - a[i] + j;
  83. if((cur & 1) || !dp[cur>>1]){
  84. f[j] = 1;
  85. }
  86. }
  87. add(a[i]);
  88. }
  89. for(int x = 1; x <= s; x++){
  90. if(!f[x]) ans.pb(x);
  91. }
  92. printf("%d\n", int(ans.size()));
  93. for(int i = 0; i < ans.size(); i++){
  94. printf("%d ", ans[i]);
  95. }
  96.  
  97. return 0;
  98. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement