Submission #714003

#	Time	Username	Problem	Language	Result	Execution time	Memory
714003		Alex_tz307	Bootfall (IZhO17_bootfall)	C++17	100 / 100	530 ms	31848 KiB

bootfall

#include <bits/stdc++.h>

using namespace std;

const int kN = 500;
const int kMax = kN * kN;
int a[1 + kN];
bitset<1 + kMax> dp, evenStr, oddStr, pref[1 + kN], suff[1 + kN + 1];

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;

  int sum = 0;

  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    sum += a[i];
  }

  pref[0][0] = true;

  for (int i = 1; i <= n; ++i) {
    pref[i] = pref[i - 1] | (pref[i - 1] << a[i]);
  }

  suff[n + 1][0] = true;

  for (int i = n; i > 0; --i) {
    suff[i] = suff[i + 1] | (suff[i + 1] << a[i]);
  }

  if (sum % 2 == 1 || !pref[n].test(sum / 2)) {
    cout << "0\n";
    return 0;
  }

  bool even = true, odd = true;

  evenStr.set();
  oddStr.set();

  evenStr[0].flip();

  for (int i = 1; i <= n; ++i) {
    if (i <= n / 2) {
      dp = suff[i + 1];

      for (int j = 1; j < i; ++j) {
        dp |= dp << a[j];
      }
    } else {
      dp = pref[i - 1];

      for (int j = i + 1; j <= n; ++j) {
        dp |= dp << a[j];
      }
    }

    int rest = sum - a[i];

    if (rest % 2 == 0) {
      if (even) {
        evenStr &= dp >> (rest / 2);
      }

      if (odd) {
        odd = false;
        oddStr = 0;
      }
    } else {
      if (odd) {
        oddStr &= dp >> (rest / 2 + 1);
      }

      if (even) {
        even = false;
        evenStr = 0;
      }
    }
  }

  cout << evenStr.count() + oddStr.count() << '\n';

  for (int i = 0; i < kMax; ++i) {
    if (evenStr.test(i)) {
      cout << 2 * i << ' ';
    } else if (oddStr.test(i)) {
      cout << 2 * i + 1 << ' ';
    }
  }

  cout << '\n';

  return 0;
}

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