Submission #579823

#	Time	Username	Problem	Language	Result	Execution time	Memory
579823		gg123_pe	Bootfall (IZhO17_bootfall)	C++14	100 / 100	749 ms	2972 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; 
const ll mod = 1e9 + 7; 


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

void add(int x){
    fa(i,s,x) {
        dp[i] = (dp[i] + dp[i-x]) % 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+j > 2*s) break; 
            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: 16 / 16
• Subtask 5: 21 / 21
• Subtask 6: 35 / 35