Submission #897471

#	Time	Username	Problem	Language	Result	Execution time	Memory
897471		AI_2512	Bootfall (IZhO17_bootfall)	C++17	13 / 100	1030 ms	500 KiB

bootfall

#include <bits/stdc++.h>
 
using namespace std;
bool canPartition(vector<int> nums) {
    int totalSum = 0;
    for (int num : nums) {
        totalSum += num;
    }
    if (totalSum % 2 != 0) {
        return false;
    }

    int targetSum = totalSum / 2;
    int n = nums.size();
    vector<vector<bool>> dp(n + 1, vector<bool>(targetSum + 1, false));
    for (int i = 0; i <= n; ++i) {
        dp[i][0] = true;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= targetSum; ++j) {
            dp[i][j] = dp[i - 1][j];
            if (j >= nums[i - 1]) {
                dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];
            }
        }
    }
    return dp[n][targetSum];
}

bool can(vector<int> vec){
    for (int i = 0; i< vec.size(); i++){
        vector<int> darr(vec.begin(), vec.end());
        darr.erase(next(darr.begin(), i));
        if (!canPartition(darr)) return false;
    }
    return true;
}

signed main(){
    int n, sum = 0;
    cin >> n;
    vector<int> vec;
    vector<int> res;
    for (int i = 0; i< n; i++){
        int a;
        cin >> a;
        vec.push_back(a);
        sum+=a;
    }

    for (int i = 1; i<= sum; i++){
        vec.push_back(i);
        if (can(vec)){
            res.push_back(i);
        }
        vec.erase(vec.end()-1);
    }
    cout << res.size() << "\n";
    for (int el:res) cout << el << " ";
    return 0;
}

Compilation message (stderr)

bootfall.cpp: In function 'bool can(std::vector<int>)':
bootfall.cpp:31:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for (int i = 0; i< vec.size(); i++){
      |                     ~^~~~~~~~~~~~

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