Submission #1092439

#TimeUsernameProblemLanguageResultExecution timeMemory
1092439juicyBootfall (IZhO17_bootfall)C++17
100 / 100
120 ms2388 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...