Submission #579820

#	Time	Username	Problem	Language	Result	Execution time	Memory
579820		gg123_pe	Bootfall (IZhO17_bootfall)	C++14	28 / 100	24 ms	388 KiB

bootfall

#include <bits/stdc++.h>
using namespace std; 

typedef long long ll; 
#define f(i,a,b) for(int i = a; i < b; i++)
#define fa(i,a,b) for(int i = a; i >= b; i--)

const int N = 1e5 + 5, M = 1e6 + 5, mod = 1e9 + 7; 


int n, s, a[505], dp[25005]; 
bitset <25005> on; 

void add(int x){
    fa(i,s,x) {
        dp[i] += dp[i-x]; 
        dp[i] %= mod; 
    }
}

void res(int x){
    f(i,x,s+1){
        dp[i] = (dp[i] - dp[i-x] + mod) % mod; 
    }
}
int main(){
    cin >> n; 

    f(i,1,n+1) {
        cin >> a[i]; 
        s += a[i]; 
    }

    dp[0] = 1; 

    f(i,1,n+1){
        add(a[i]); 
    }

    if(s&1 or dp[s/2] == 0){
        cout << "0\n"; 
        return 0; 
    }

    f(i,1,s+1) on[i] = 1;       

    f(i,1,n+1){
        res(a[i]); 

        int x = s - a[i]; 
        f(j,1,s+1){
            if(x%2 != j%2 or dp[(x+j)/2] == 0) on[j] = 0;
        }
        add(a[i]); 
    }
    cout << on.count() << "\n";  
    f(i,1,s+1) if(on[i]) cout << i << " "; 
    cout << "\n"; 

    return 0; 
}

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