Submission #679696

#TimeUsernameProblemLanguageResultExecution timeMemory
679696vjudge1Bootfall (IZhO17_bootfall)C++14
65 / 100
1090 ms3024 KiB
#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pb push_back
#define all(a) a.begin(), a.end()

typedef long long ll;
typedef pair<int, int> ii;

const int N = 500 + 5;
const ii mod = {1e9 + 7, 1e9 + 21};

ii dp[N * N];
int n, sum;
int a[N], cnt[N * N];

void fix(int &a, const int &mod)
{
    if(a >= mod) a -= mod;
    if(a < 0) a += mod;
}

void add(int x)
{
    for(int i = sum; i >= x; i--)
    {
        dp[i].F += dp[i - x].F;
        dp[i].S += dp[i - x].S;
        fix(dp[i].F, mod.F), fix(dp[i].S, mod.S);
    }
}

void del(int x)
{
    for(int i = x; i <= sum; i++)
    {
        dp[i].F -= dp[i - x].F;
        dp[i].S -= dp[i - x].S;
        fix(dp[i].F, mod.F), fix(dp[i].S, mod.S);
    }
}

void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i], sum += a[i];
    if(sum & 1) cout << 0, exit(0);
    
    int tmp = sum;
    sum /= 2;
    dp[0] = {1, 1};
    for(int i = 1; i <= n; i++) 
        add(a[i]);
    if(dp[sum].F == 0 && dp[sum].S == 0) 
        cout << 0, exit(0);
        
    for(int i = 1; i <= n; i++)
    {
        del(a[i]);
        tmp -= a[i];
        vector<int> s;
        for(int i = 0; i <= tmp / 2; i++)
            if(dp[i].F != 0 || dp[i].S != 0)
            {
                int team1 = i;
                int team2 = tmp - team1;
                s.pb(abs(team1 - team2));
            }
        sort(all(s));
        s.resize(unique(all(s)) - s.begin());
        for(int x : s) cnt[x]++;
        
        tmp += a[i];
        add(a[i]);
    }
    
    vector<int> res;
    for(int i = 1; i <= 500 * 500; i++)
        if(cnt[i] == n) res.pb(i);
    cout << res.size() << '\n';
    for(const int &x : res) cout << x << ' ';
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    // cin >> t;
    while(t--) 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...