Submission #954083

#	Time	Username	Problem	Language	Result	Execution time	Memory
954083		nguyennh	Bootfall (IZhO17_bootfall)	C++14	13 / 100	1024 ms	816 KiB

bootfall

#include<bits/stdc++.h>
#define el '\n'
using namespace std ;

const int MN = 1e5 + 5;

int n;

namespace sub_trau{
  int64_t dp[MN];
  
  // check whether existing a way to divide array into 2 parts with sum = x;
  void solve(){
    vector<int> a(n + 5);
    for ( int i = 1 ; i <= n ; i++ ) cin >> a[i];
    if (n & 1){
      cout << 0;
      return;
    }
    bool odd = false , even = false;
    for ( int i = 1 ; i <= n ; i++ ){
      odd |= (a[i] & 1);
      even |= (a[i] % 2 == 0);
    }
    if (odd && even){
      cout << 0;
      return;
    }
    bitset<MN> bit;
    bit[0] = 1;
    for ( int i = 1 ; i <= n ; i++ ) bit |= (bit << a[i]);
    int sum = accumulate(a.begin() + 1 , a.begin() + n + 1 , 0);
    int mn = *min_element(a.begin() + 1 , a.begin() + n + 1); 
    if (!bit[sum / 2]){
      cout << 0;
      return;
    }
    dp[0] = 1;
    for ( int i = 1 ; i <= n ; i++ ){
      for ( int j = sum ; j >= a[i] ; j-- ) dp[j] += dp[j - a[i]];
    }
    vector<int> ans , candidates;
    for ( int i = 1 ; i <= n ; i++ ) candidates.push_back(a[i]);
    for ( int val = odd ? 1 : 2 ; val <= sum - mn ; val += 2 ){
      int all = sum + val;
      candidates.push_back(val);
      for ( int j = all ; j >= val ; j-- ) dp[j] += dp[j - val];
      bool check = true;
      for ( int turn = 0 ; turn < n ; turn++ ){
        if (!check) break;
        int need = all - candidates[turn];
        if (need & 1){
          check = false;
          break;
        }
        for ( int j = candidates[turn] ; j <= need / 2 ; j++ ){
          dp[j] -= dp[j - candidates[turn]];
        }
        if (!dp[need / 2]){
          check = false;
        }
        for ( int j = need / 2 ; j >= candidates[turn] ; j-- ) dp[j] += dp[j - candidates[turn]];
      }
      if (check) ans.push_back(val);
      candidates.pop_back();
      for ( int j = val ; j <= all ; j++ ) dp[j] -= dp[j - val];
    }
    cout << ans.size() << el;
    for ( auto x : ans ) cout << x << " ";
  }
}

int32_t main (){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  sub_trau::solve();
}

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