Submission #1338118

#TimeUsernameProblemLanguageResultExecution timeMemory
1338118DangKhoizzzzBootfall (IZhO17_bootfall)C++20
65 / 100
1047 ms1196 KiB
#include <bits/stdc++.h>
#define int long long
#define arr3 array <int , 3>
#define pii pair <int , int>
#define fi first
#define se second
#define BIT(x , k) ((x >> k)&1)
#define MASK(x) (1 << x)

using namespace std;

const int maxn = 500*500 + 10;
const int INF = 1e18;

int n, a[maxn];
bitset <maxn> ans;
bitset <maxn> dp;

void solve()
{
    cin >> n;
    dp.reset(); dp[0] = 1;
    int sum = 0;
    for(int i = 1; i <= n; i++) 
    {
        cin >> a[i];
        sum += a[i];
        dp |= (dp << a[i]);
    }
    if(sum % 2 == 1 || dp[sum/2] == 0) {cout << 0 << '\n'; return;}
    ans.reset(); ans.flip();

    for(int i = 1; i <= n; i++)
    {
        dp.reset();
        dp[0] = 1;
        for(int j = 1; j <= n; j++)
        {
            if(i != j) dp |= (dp << a[j]);
        }
        bitset <maxn> tmp;
        for(int j = 0; 2*j <= sum - a[i]; j++)
        {
            if(dp[j] && (sum - a[i] - 2*j)) tmp[sum - a[i] - 2*j] = 1;
        }
        ans &= tmp;
    }
    vector <int> print;
    for(int i = 0; i < 500*500; i++) 
    {
        if(ans[i]) print.push_back(i);
    }
    cout << print.size() << '\n';
    for(int x: print) cout << x << ' ';
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    solve();
    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...