Submission #714009

#	Time	Username	Problem	Language	Result	Execution time	Memory
714009		Alex_tz307	Bootfall (IZhO17_bootfall)	C++17	65 / 100	1092 ms	23444 KiB

bootfall

#include <bits/stdc++.h>

using namespace std;

const int mod[] = {(int)1e9 + 7, (int)1e9 + 9};

void addSelf(int &x, int y, int mod) {
  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<vector<int>> dp(sum + 1, vector<int>(2));

  dp[0][0] = dp[0][1] = 1;

  for (const int &x : a) {
    for (int i = sum; i >= x; --i) {
      for (int j = 0; j < 2; ++j) {
        addSelf(dp[i][j], dp[i - x][j], mod[j]);
      }
    }
  }

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

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

  vector<vector<int>> newDp(sum + 1, vector<int>(2));

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

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

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

      if (newSum % 2 == 1 || newDp[newSum / 2] == vector<int>(2)) {
        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: 0 / 35