Submission #233716

#	Time	Username	Problem	Language	Result	Execution time	Memory
233716		Haunted_Cpp	Bootfall (IZhO17_bootfall)	C++17	44 / 100	1091 ms	760 KiB

bootfall

#include <bits/stdc++.h>
using namespace std;

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

bitset<S> ans;
bitset<S> is_possible;
bitset<S> Get;

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++) {
    int was = a[i];    
    a[i] = 0;
    whole_sum -= was;
    
    is_possible.reset();
    is_possible[0] = 1;
    for (int j = 0; j < n; j++) {
      is_possible |= (is_possible << a[j]);
    }
    
    Get.reset();
    
    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;
}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 15 / 15
• Subtask 4: 16 / 16
• Subtask 5: 0 / 21
• Subtask 6: 0 / 35