Submission #522953

#	Time	Username	Problem	Language	Result	Execution time	Memory
522953		nickmet2004	Bootfall (IZhO17_bootfall)	C++11	100 / 100	577 ms	3440 KiB

bootfall

#include<bits/stdc++.h>

using namespace std;
const int N = 501;
int n , a[N] , dp[N*N+505] , ans[N * N];
int main (){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    int s =0;
    for(int i = 0;i < n; ++i)cin >> a[i] ,s+=a[i];
    dp[0] = 1;
    for(int i = 0; i < n; ++i){
        for(int j = s; j>= a[i]; --j)dp[j] += dp[j - a[i]];
    }
    if(s & 1 || dp[s/2]==0){
        cout << 0; return 0;
    }
    vector<int> y;
    for(int i = 0; i <n; ++i){
        for(int j = a[i]; j <= s; ++j)dp[j] -= dp[j - a[i]];
        for(int j = 1; j<= s; ++j){
            int z = s - a[i] + j;
            //cout << j << " " << S << endl;
            if(z&1 || !dp[z/2])continue;
            ans[j]++;
            if(ans[j]==n)y.emplace_back(j);
        }
        for(int j = s; j >= a[i]; --j)dp[j] += dp[j-a[i]];
    }
    cout << y.size()<<endl;
    for(int x : y)cout << x << " ";

    //cout << dp[s/2];
}

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