Submission #858302

#	Time	Username	Problem	Language	Result	Execution time	Memory
858302		Alfraganus	Bootfall (IZhO17_bootfall)	C++17	100 / 100	877 ms	16948 KiB

bootfall

#include <bits/stdc++.h>
using namespace std;

#define fs first
#define ss second
#define endl '\n'
#define all(a) a.begin(), a.end()

#define print(a)          \
    for(auto x : a)       \
        cout << x << ' '; \
    cout << endl;

#define printmp(a)   \
    for (auto x : a) \
        cout << x.fs << ' ' << x.ss << endl;

void solve(){
    int n, s = 0;
    cin >> n;
    vector<int> a(n);
    bool juft = true, toq = true;
    for(int i = 0; i < n; i ++)
        cin >> a[i], s += a[i], juft &= (a[i] % 2 == 0), toq &= (a[i] % 2 == 1);
    if(s % 2 == 1 or juft == toq){
        cout << 0;
        return;
    }
    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][i] = 1;
                }
                else
                    dp[j] = dp[j] & dp[j - a[i]];
                can[j] = true;
            }
        }
    }
    if(!can[s / 2]){
        cout << 0;
        return;
    }
    vector<int> ans;
    for(int x = 0; x <= s; x ++){
        bool flag = (s - a[0] + x) % 2 == 0;
        for(int j = 0; j < n; j ++){
            if(can[(s - a[j] + x) / 2] and !dp[(s - a[j] + x) / 2][j])
                continue;
            else{
                flag = 0;
                break;
            }
        }
        if(flag)
            ans.push_back(x);
    }
    cout << ans.size() << endl;
    print(ans)
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while(t --){
        solve();
        cout << endl;
    }
}

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