Submission #38275

#	Time	Username	Problem	Language	Result	Execution time	Memory
38275		Just_Solve_The_Problem	Bootfall (IZhO17_bootfall)	C++11	100 / 100	359 ms	4116 KiB

bootfall

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define ok puts("ok");

const int NN = 505;
const int N = NN * NN;

int a[NN];
int dp[N];
bool used[NN], can[N];
int sum;

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

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

main () {
    int n; scanf ("%d", &n);
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        scanf ("%d", a + i);
        add(a[i]);
    }
    if ((sum & 1) || !dp[sum / 2]) {
        puts("0");
        return 0;
    }
    for (int i = 0; i < N; i++) can[i] = 1;
    for (int i = 1; i <= n; i++) {
        if (used[a[i]]) continue;
        used[a[i]] = 1;
        del(a[i]);
        for (int j = 0; j < N; j++) {
            if (((sum + j) & 1) || !dp[(sum + j) / 2]) {
                can[j] = 0;
            }
        }
        add(a[i]);
    }
    vector < int > ans;
    for (int i = 0; i < N; i++) {
        if (can[i]) {
            ans.pb(i);
        }
    }
    cout << ans.size() << endl;
    for (int to : ans) {
        cout << to << ' ';
    }
}

Compilation message (stderr)

bootfall.cpp:30:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
bootfall.cpp: In function 'int main()':
bootfall.cpp:31:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int n; scanf ("%d", &n);
                            ^
bootfall.cpp:34:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d", a + i);
                            ^

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