제출 #1338126

#제출 시각아이디문제언어결과실행 시간메모리
1338126DangKhoizzzzBootfall (IZhO17_bootfall)C++20
0 / 100
9 ms4256 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;
const int mod = (1ll << 61) - 1e9 + 7;

int n, a[maxn];
bitset <maxn> ans;
bitset <maxn> tmp;
vector <int> dp(maxn , 0);
int sum = 0;

void solve()
{
    cin >> n;
    dp[0] = 1;
    for(int i = 1; i <= n; i++) 
    {
        cin >> a[i];
        sum += a[i];
        for(int j = maxn-1; j >= a[i]; j--) (dp[j] += dp[j - a[i]]) %= mod;
    }
    ans.reset(); ans.flip();

    for(int i = 1; i <= n; i++)
    {
        vector <int> ndp = dp;
        for(int j = a[i]; j < maxn; j++) (ndp[j] -= ndp[j - a[i]] + mod) %= mod;
        tmp.reset();
        for(int j = 0; 2*j <= sum - a[i] ; j++)
        {
            if(ndp[j] != 0) tmp[sum - a[i] - 2*j] = 1;
        }
        ans &= tmp;
    }
    cout << ans.count() << '\n';
    for(int i = 0; i < maxn; i++) 
    {
        if(ans[i]) cout << i << ' ' ;
    }
}

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...