Submission #36144

#	Time	Username	Problem	Language	Result	Execution time	Memory
36144		minhtung0404	Bootfall (IZhO17_bootfall)	C++14	65 / 100	1000 ms	3920 KiB

bootfall

#include<bits/stdc++.h>
const int N = 505;
const int mod = 1e9 + 7;
using namespace std;

vector <int> dp[2];
int n, sum, a[N], cnt;
bool ck[N*N];

void add(int& a, int b){
    a += b; if (a >= mod) a -= mod;
}

void sub(int& a, int b){
    a -= b; if (a < 0) a += mod;
}

void solve(int num){
    for (int i = 0; i <= sum; i++){
        dp[1][i] = dp[0][i];
        if (i >= a[num]) sub(dp[1][i], dp[1][i-a[num]]);
        if (dp[1][i] == 0 && 2*i+a[num]-sum >= 0) ck[2*i+a[num]-sum] = 1;
    }
}

int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {scanf("%d", &a[i]); sum += a[i];}
    dp[0].assign(sum+1, 0); dp[1].assign(sum+1, 0); dp[0][0] = 1;
    for (int i = 1; i <= n; i++){
        for (int j = 0; j <= sum; j++){
            dp[1][j] = dp[0][j];
            if (j >= a[i]) add(dp[1][j], dp[0][j-a[i]]);
        }
        dp[0].swap(dp[1]);
    }
    if (sum % 2 == 1 || dp[0][sum/2] == 0){
        printf("0");
        return 0;
    }
    int check = a[1]%2;
    for (int i = 1; i <= n; i++) if (a[i] % 2 != check) {check = -1; break;}
    if (check == -1) {
        printf("0");
        return 0;
    }
    for (int i = 1; i <= n; i++) solve(i);
    for (int i = check; i <= sum; i+=2) if (ck[i] == 0) cnt++;
    printf("%d\n", cnt);
    for (int i = check; i <= sum; i+=2) if (ck[i] == 0) printf("%d ", i);
}

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:27:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
bootfall.cpp:28:53: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 1; i <= n; i++) {scanf("%d", &a[i]); sum += a[i];}
                                                     ^

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