Submission #404450

#	Time	Username	Problem	Language	Result	Execution time	Memory
404450		rama_pang	Bootfall (IZhO17_bootfall)	C++17	100 / 100	618 ms	3452 KiB

bootfall

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

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

  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }

  const int MAX = accumulate(begin(A), end(A), 0) + 5;
  const int MOD = 1e9 + 7;
  const auto Add = [&](int &a, int b) {
    a += b;
    if (a >= MOD) a -= MOD;
  };

  int sum = 0;
  vector<int> dp(MAX);

  dp[0] = 1;

  const auto Insert = [&](int a) {
    sum += a;
    for (int i = MAX - 1; i >= 0; i--) {
      if (i + a < MAX) {
        Add(dp[i + a], dp[i]);
      }
    }
  };

  const auto Delete = [&](int a) {
    sum -= a;
    for (int i = 0; i < MAX; i++) {
      if (i + a < MAX) {
        Add(dp[i + a], MOD - dp[i]);
      }
    }
  };

  for (int i = 0; i < N; i++) {
    Insert(A[i]);
  }

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

  vector<int> ans(MAX);
  for (int i = 0; i < N; i++) {
    Delete(A[i]);
    for (int j = 1; j < MAX; j++) {
      int nsum = sum + j;
      if (nsum % 2 != 0) continue;
      int need = nsum / 2;
      if ((0 <= need - 0 && need - 0 < MAX && dp[need - 0] != 0) ||
          (0 <= need - j && need - j < MAX && dp[need - j] != 0)) {
        ans[j]++;
      }
    }
    Insert(A[i]);
  }

  vector<int> answer;
  for (int i = 1; i < MAX; i++) {
    if (ans[i] == N) {
      answer.emplace_back(i);
    }
  }

  cout << answer.size() << '\n';
  for (auto a : answer) {
    cout << a << ' ';
  }
  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