제출 #679696

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
679696		vjudge1	Bootfall (IZhO17_bootfall)	C++14	65 / 100	1090 ms	3024 KiB

bootfall

#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;
}

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