Submission #1155690

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155690		dinh	Bootfall (IZhO17_bootfall)	C++17	13 / 100	418 ms	326496 KiB

bootfall

#include<bits/stdc++.h> 

using namespace std;

/*
   3 5 7 11 9 13
     
 */
vector<int> solve(vector<int>& nums) {

  int sum = 0;
  for (auto x: nums) {
    sum += x;
  }
  nums.push_back(0);

  vector<vector<vector<int>>> dp(nums.size()+1, vector<vector<int>>(nums.size()+1, vector<int>(sum + 1)));
  for (int i=0;i<=nums.size();i++) {
    for (int j=0;j<=nums.size();j++) {
      dp[i][j][0] = true;
    }
  }


  for (int i=1;i<=nums.size();i++) {
    for (int s=1;s<=sum;s++) {
      for (int j=1;j<=nums.size();j++) {
        dp[i][j][s] |= dp[i][j-1][s];
        if (j != i && s >= nums[j - 1]) {
          dp[i][j][s] |= dp[i][j-1][s - nums[j-1]];
        }
        // cout << dp[i][j][s] << ' ';
      }
      // cout << endl;
    }
    // cout << endl;
  }
  
  vector<int> res;
  for (int x=1;x<=sum;x++) {
    int ok = true;
    for (int i=1;i<nums.size();i++) {
      int target = sum - nums[i-1] + x;
      if (target % 2 == 1) {
        ok = false;
        break;
      }

      if (!dp[i][nums.size()-1][target / 2]) {
        ok = false;
        break;
      }
        
    }
    
    if (ok && dp[nums.size()][nums.size()][sum / 2] && sum % 2 == 0) {
      res.push_back(x);
    }
  }

  return res;
}

int main() {
  int n;
  cin >> n;

  vector<int> nums(n);
  for (int i=0;i<n;i++) {
    cin >> nums[i];
  }

  auto res = solve(nums);
  cout << res.size() << endl;
  for (auto x: res)
    cout << x << ' ';
  return 0;
}
/*
  3 5 7 11 9 13

  x

  
    
*/

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