Submission #1293985

#TimeUsernameProblemLanguageResultExecution timeMemory
1293985gsalterBootfall (IZhO17_bootfall)C++20
13 / 100
1095 ms584 KiB
/*
22 Nov 2025
*/
#include <iostream>
#include <vector>
 
using namespace std;
 
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];
    }
    // cout << max_x << endl;
    // iterate through possible x
    vector<int> res;
    for (int x=1; x<=max_x; x++) {
        // cout << "x = " << x << endl;
        // fix x
        bool friendly = true;
        w[n] = x;
        for (int i=0; i<=n; i++) {
            // remove w[i] from the array
            int max_s = max_x - w[i] + x;
            if (max_s%2 != 0) { friendly = false; break; }
            int half = max_s / 2;
            vector<int> dp(half+1, 0);
            dp[0] = 1;
            // cout << "Can we get " << half << " from {";
            for (int j=0; j<=n; j++) {
                if (j==i) continue;
                // cout << w[j] << ", ";
                for (int s=half; s>=w[j]; s--) {
                    dp[s] += dp[s - w[j]];
                }
            }
            // cout << x << "} ? ";
            if (dp[half] > 0) {
                // cout << "Yes" << endl;
            }
            else { 
                // cout << "No" << endl; 
                friendly = false;
                break;
            }
        }
        if (friendly) {
            res.push_back(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...