Submission #857601

#	Time	Username	Problem	Language	Result	Execution time	Memory
857601		sunnat	Bootfall (IZhO17_bootfall)	C++14	100 / 100	751 ms	16912 KiB

bootfall

#include <bitset>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int main(){
    int n;
    cin >> n;
    if(n % 2 != 0){
        cout << 0;
        return 0;
    }
    vector<int> a(n);
    for(int i = 0; i < n; i ++) cin >> a[i];
    int k = a[0] & -a[0], s = 0;
    for(int i = 0; i < n; i ++){
        if((a[i] & -a[i]) != k){
            cout << 0;
            return 0;
        }
        a[i] /= k;
        s += a[i];
    }
    vector<bitset<500>> dp(s+1);
    vector<bool> can(s+1);
    can[0] = true;
    int s1 = 0;
    for(int i = 0; i < n; i ++){
        s1 += a[i];
        for(int j = s1; j >= a[i]; j --){
            if(can[j - a[i]]){
                if(!can[j]){
                    dp[j] = dp[j-a[i]];
                    dp[j].set(i, 1);
                }
                else dp[j] = dp[j] & dp[j-a[i]];
                can[j] = true;
            }
        }
    }
    if(!can[s/2]){
        cout << 0;
        return 0;
    }
    vector<int> res;
    for(int x = 1; x <= s; x += 2){
        bool f = true;
        for(int i = 0; i < n; i ++)
            if(!can[(s + x - a[i]) / 2] || dp[(s + x - a[i]) / 2][i]){
                f = false;
                break;
            }
        if(f)
            res.push_back(x);
    }
    cout << res.size() << '\n';
    for(int x:res) cout << x * k << ' ';
    return 0;
}

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