Submission #1208684

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208684		lopkus	Bootfall (IZhO17_bootfall)	C++20	6 / 100	4 ms	4744 KiB

bootfall

#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 - x) % 2 == 0 && dp[n][(t - 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;
}

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