제출 #233715

#제출 시각아이디문제언어결과실행 시간메모리
233715Haunted_CppBootfall (IZhO17_bootfall)C++17
44 / 100
1045 ms636 KiB
#include <bits/stdc++.h>
using namespace std;

const int N = 5e2 + 5;
const int S = N * N;

bitset<S> ans;

int main () {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> a (n + 1);
  for (int i = 0; i < n; i++) cin >> a[i];
  ans.set();
  int whole_sum = accumulate (a.begin(), a.end(), 0);
  for (int i = 0; i <= n; i++) {
   // i = n;
    int was = a[i];    
    a[i] = 0;
    whole_sum -= was;
    bitset<S> is_possible;
    is_possible[0] = 1;
    for (int j = 0; j < n; j++) {
      is_possible |= (is_possible << a[j]);
    }
    bitset<S> Get;
    bool is_there_valid = false;
    for (int j = 0; j <= whole_sum; j++) {
      if (is_possible[j]) {
        int left = j;
        int right = whole_sum - j;
     //   cout << left << ' ' << right << '\n';
        if (i == n && left == right) is_there_valid = true;
        Get[abs(left - right)] = 1;
      }
    }
    
    if (i == n) {
      if (!is_there_valid) {
        cout << 0 << '\n';
        return 0;
      } else break;
    }
    
    ans &= Get;
    whole_sum += was;
    a[i] = was;
  }
  
  cout << ans.count() << '\n';
  for (int i = 0; i < S; i++) if (ans[i]) cout << i << ' ';
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...