Submission #1208685

#TimeUsernameProblemLanguageResultExecution timeMemory
1208685lopkusBootfall (IZhO17_bootfall)C++20
13 / 100
557 ms326456 KiB
#include <bits/stdc++.h>

#define int long long

void solve() {
  int n;
  std::cin >> n;
  std::vector<int> a(n + 1);
  for(int i = 1; i <= n; i++) {
    std::cin >> a[i];
  }
  int sum = 0;
  for(int i = 1; i <= n; i++) {
    sum += a[i];
  }
  const int N = sum + 5;
  int dp[n + 1][N][n + 1];
  for(int i = 0; i <= n; i++) {
    for(int sum = 0; sum < N; sum++) {
      for(int j = 0; j <= n; j++) {
        dp[i][sum][j] = 0;
      }
    }
  }
  for(int i = 0; i <= n; i++) {
    dp[0][0][i] = 1;
  }
  for(int i = 1; i <= n; i++) {
    for(int j = 0; j <= n; j++) {
      for(int sum = 0; sum < N; sum++) {
        dp[i][sum][j] = dp[i - 1][sum][j];
      }
      if(i != j) {
        for(int sum = a[i]; sum < N; sum++) {
          dp[i][sum][j] |= dp[i - 1][sum - a[i]][j];
        }
      }
    }
  }
  for(int i = 0; i <= n; i++) {

  }
  std::vector<int> ans;
  for(int x = 0; x < N; x++) {
    int ok = 1;
    if(sum % 2 == 0) {
      ok &= dp[n][sum / 2][0];
    }
    for(int i = 1; i <= n; i++) {
      int t = sum;
      t += x;
      t -= a[i];
      int k = 0;
      if(t % 2 == 0) {
        if(dp[n][t / 2][i] == 1) {
          k = 1;
        }
        else {
        }
      }
      if(t >= 2 * x && ((t - 2 * x) % 2 == 0 && dp[n][(t - 2 * x) / 2][i] == 1)) {
        k = 1;
      }
      if(!k) {
        ok = 0;
        break;
      }
    }
    if(ok) {
      ans.push_back(x);
    }
  }
  std::cout << ans.size() << "\n";
  for(int i = 0; i < ans.size(); i++) {
    std::cout << ans[i] << " ";
  }
}

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

  int t = 1;
  //std::cin >> t;
  while (t--) {
      solve();
  }

  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...