Submission #1293976

#TimeUsernameProblemLanguageResultExecution timeMemory
1293976gsalterBootfall (IZhO17_bootfall)C++20
13 / 100
674 ms584 KiB
/*
*/
#include <iostream>
#include <vector>
 
using namespace std;
 
void print(const vector<int>& vec) {
    for (int i=0; i<vec.size(); i++) {
        cout << vec[i] << ' ';
    }
    cout << '\n';
}

int main() {
    int n;
    cin >> n;
    vector<int> w(n+1, 0);
    int max_x = 0;
    for (int i=0; i<n; i++) {
        cin >> w[i];
        max_x += w[i];
    }
    vector<int> res;
    // cout << max_x << '\n';
    // iterate through possible x
    for (int x=1; x<=max_x; x++) {
        // cout << "x = " << x << '\n';
        // fix x
        w[n] = x;
        max_x += x;
        // print(w);
        vector<int> dp(max_x + 1, 0);
        dp[0] = 1;

        // add everything to knapsack
        for (int i=0; i<=n; i++) {
            for (int s=max_x; s>=w[i]; s--) {
                dp[s] += dp[s-w[i]];
            }
        }
        
        // print(dp);
        
        bool friendly = true;
        for (int i=0; i<=n; i++) {
            if (!friendly) break;
            int max_s = max_x - w[i];
            if (max_s%2 != 0) {
                // cout << max_s << " is not even, cannot split\n";
                friendly = false;
                break;   
            }
            // remove w[i]
            // cout << "removed " << w[i] << '\n';
            for (int s=w[i]; s<=max_x; s++) {
                dp[s] -= dp[s - w[i]];
            }
            int half = max_s / 2;
            if (dp[half] > 0) {
                // cout << "We can split " << max_s << " in half\n";
            } else {
                // cout << " We cannot split " << max_s << " in half\n";
                friendly = false;
            }
            // print(dp);
            // add back w[i]
            for (int s=max_x; s>=w[i]; s--) {
                dp[s] += dp[s - w[i]];
            }
            // cout << "added back " << w[i] << '\n';
        }

        if (friendly) {
            // cout << x << " is friendly\n";
            res.push_back(x);
        }

        // print(dp);
        max_x -= x;
    }

    cout << res.size() << '\n';
    for (int i=0; i<res.size(); i++) {
        cout << res[i] << ' ';
    }
    cout << '\n';
    
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...