Submission #714012

#	Time	Username	Problem	Language	Result	Execution time	Memory
714012		Alex_tz307	Bootfall (IZhO17_bootfall)	C++17	100 / 100	577 ms	2904 KiB

bootfall

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;

void addSelf(int &x, int y) {
  x += y;
  if (x >= mod) {
    x -= mod;
  }
}

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

  int n;
  cin >> n;

  vector<int> a(n);

  for (int &x : a) {
    cin >> x;
  }

  int sum = accumulate(a.begin(), a.end(), 0);

  vector<int> dp(sum + 1);

  dp[0] = 1;

  for (const int &x : a) {
    for (int i = sum; i >= x; --i) {
      addSelf(dp[i], dp[i - x]);
    }
  }

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

  vector<bool> wt(sum + 1, true);

  vector<int> newDp(sum + 1);

  for (const int &x : a) {
    newDp = dp;

    for (int i = x; i <= sum; ++i) {
      addSelf(newDp[i], mod - newDp[i - x]);
    }

    for (int i = 1; i <= sum; ++i) {
      int newSum = sum - x + i;

      if (newSum % 2 == 1 || newDp[newSum / 2] == 0) {
        wt[i] = false;
      }
    }
  }

  cout << count(wt.begin() + 1, wt.end(), true) << '\n';

  for (int i = 1; i <= sum; ++i) {
    if (wt[i]) {
      cout << i << ' ';
    }
  }

  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