Submission #679698

#	Time	Username	Problem	Language	Result	Execution time	Memory
679698		vjudge1	Bootfall (IZhO17_bootfall)	C++14	100 / 100	680 ms	2956 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 int mod = 1e9 + 21;

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

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

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

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

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;
    for(int i = 1; i <= n; i++) 
        add(a[i]);
    if(dp[sum]== 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] != 0)
        {
            int team1 = i;
            int team2 = tmp - team1;
            cnt[abs(team1 - team2)]++;
        }
        
        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: 35 / 35