Submission #1208719

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208719		lopkus	Bootfall (IZhO17_bootfall)	C++20	65 / 100	1096 ms	3132 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 = 500 * 500 + 501;
  /**
  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];
        }
      }
    }
  }**/
  std::vector<int> cnt(N);
  for(int j = 0; j <= n; j++) {
    std::bitset<N> newdp;
    newdp[0] = 1;
    for(int i = 1; i <= n; i++) {
      if(i != j) {
        newdp |= (newdp << a[i]);
      }
    }
    for(int i = 0; i < N; i++) {
      int t = sum;
      if(j == 0) {
        if(sum % 2 == 0 && newdp.test(sum / 2)) {
          cnt[i] += 1;
        }
        continue;
      }
      t += i;
      t -= a[j];
      int k = 0;
      if(t < N && t % 2 == 0 && newdp.test(t / 2)) {
        k = 1;
      }
      t -= 2 * i;
      if(t >= 0 && t % 2 == 0 && newdp.test(t / 2)) {
        k = 1;
      }
      cnt[i] += k;
    }
  }
  std::vector<int> ans;
  for(int x = 0; x < N; x++) {
    if(cnt[x] == n + 1) {
      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: 7 / 7
• Subtask 3: 15 / 15
• Subtask 4: 16 / 16
• Subtask 5: 21 / 21
• Subtask 6: 0 / 35