Submission #990181

#	Time	Username	Problem	Language	Result	Execution time	Memory
990181		tch1cherin	Bootfall (IZhO17_bootfall)	C++17	28 / 100	80 ms	1168 KiB

bootfall

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

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N;
  cin >> N;
  vector<int> a(N);
  for (int &value : a) {
    cin >> value;
  }
  int S = accumulate(a.begin(), a.end(), 0);
  for (int i = 0; i < N; i++) {
    if (a[i] % 2 != a[0] % 2 || S % 2) {
      cout << "0\n";
      exit(0);
    }
  }
  vector<uint64_t> rnd(N);
  mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  for (int i = 0; i < N; i++) {
    rnd[i] = rng();
  }
  vector<uint64_t> dp(S + 1);
  dp[0] = 1;
  for (int i = 0; i < N; i++) {
    for (int j = S - a[i]; j >= 0; j--) {
      dp[j + a[i]] += dp[j];
    }
  }
  if (dp[S / 2] == 0) {
    cout << "0\n";
    exit(0);
  }
  vector<bool> good(S + 1, true);
  for (int i = 0; i < N; i++) {
    for (int j = 0; j + a[i] <= S; j++) {
      dp[j + a[i]] -= dp[j];
    }
    vector<bool> new_good(S + 1);
    for (int j = 0; j <= S; j++) {
      if (dp[j] > 0) {
        new_good[abs(2 * j - (S - a[i]))] = true;
      }
    }
    for (int j = 0; j <= S; j++) {
      good[j] = good[j] && new_good[j];
    }
    for (int j = S - a[i]; j >= 0; j--) {
      dp[j + a[i]] += dp[j] * rnd[i];
    }
  }
  vector<int> answer;
  for (int i = 1; i <= S; i++) {
    if (good[i]) {
      answer.push_back(i);
    }
  }
  int k = (int)answer.size();
  cout << k << "\n";
  for (int i = 0; i < k; i++) {
    cout << answer[i] << " \n"[i + 1 == k];
  }
}

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