Submission #1092439

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092439		juicy	Bootfall (IZhO17_bootfall)	C++17	100 / 100	120 ms	2388 KiB

bootfall

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 505, M = 125005;

int n;
int a[N], f[M], cnt[2 * M];

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

  cin >> n;
  f[0] = 1;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    for (int j = M - 1; j >= a[i]; --j) {
      f[j] += f[j - a[i]];
    }
  }
  int sum = accumulate(a + 1, a + n + 1, 0);
  if (!f[sum / 2]) {
    cout << 0 << "\n";
    exit(0);
  }
  for (int i = 1; i <= n; ++i) {
    sum -= a[i];
    for (int j = a[i]; j < M; ++j) {
      f[j] -= f[j - a[i]];
    }
    for (int j = 0; j <= sum / 2; ++j) {
      if (f[j]) {
        ++cnt[sum - 2 * j];
      }
    }
    for (int j = M - 1; j >= a[i]; --j) {
      f[j] += f[j - a[i]];
    }
    sum += a[i];
  }
  int res = 0;
  for (int i = 1; i < 2 * M; ++i) {
    res += cnt[i] == n;
  }
  cout << res << "\n";
  for (int i = 1; i < 2 * M; ++i) {
    if (cnt[i] == n) {
      cout << i << " ";
    }
  }
  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