Submission #1270439

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270439		reginox	Bootfall (IZhO17_bootfall)	C++20	65 / 100	1012 ms	1720 KiB

bootfall

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(v) begin(v), end(v)
#define pi pair<int, int>
#define vi vector<int>
using namespace std;
const int N = 5e2;
int n, a[N+2];
int cnt[N*N+2];
int main(){
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n;
  for(int i = 1; i <= n; i++) cin >> a[i];
  int su = accumulate(a+1, a+n+1, 0);
  int mx = *max_element(a+1, a+n+1);
  bitset<N*N> dp;
  dp.reset();
  dp[0] = 1;
  for(int i = 1; i <= n; i++) dp |= (dp << a[i]);
  if(su % 2 != 0 || !dp[su/2]){
    cout << 0;
    return 0;
  }
  if(su - mx < 1){
    cout << 0;
    return 0;
  }
  for(int i = 1; i <= n; i++){
    bitset<N*N> dp2;
    dp2.reset();
    dp2[0] = 1;
    for(int j = 1; j <= n; j++)
      if(i != j) dp2 |= (dp2 << a[j]);
    vector<bool> ck(su-mx+1, 0);
    for(int j = 0; j <= su - a[i]; j++){
      if(dp2[j]){
        int x = abs(su-a[i]-2*j);
        if(x >= 1 && x <= su - mx){
          if(!ck[x]){
            ck[x] = true;
            cnt[x]++;
          }
        }
      }
    }
  }
  vector<int> ans;
  for(int i = 1; i <= N*N; i++){
    if(cnt[i] == n) ans.push_back(i);
  }
  cout << ans.size() << "\n";
  for(auto x:ans) cout << x << " ";
  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