Submission #849864

#	Time	Username	Problem	Language	Result	Execution time	Memory
849864		vjudge1	Bootfall (IZhO17_bootfall)	C++17	100 / 100	362 ms	4948 KiB

bootfall

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

#define NMAX 500
int n, arr[NMAX + 5];
bitset<250001> a, b;
long long f[NMAX * NMAX + 5], g[NMAX * NMAX + 5], sum;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen("ESPORT.INP", "r")) {
        freopen("ESPORT.INP", "r", stdin);
        freopen("ESPORT.OUT", "w", stdout);
    }
    cin >> n;
    sum = 0;
    for(int i = 1; i <= n; i++) {
        cin >> arr[i];
        sum += arr[i];
    }
    a.reset();
    for(int i = 1; i <= sum; i++)
        a.set(i);
    f[0] = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = sum; j >= arr[i]; j--) {
            f[j] += f[j - arr[i]];
        }
    }
    if(sum % 2 || !f[sum / 2]) {
        cout << 0;
        return 0;
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= sum; j++) {
            g[j] = f[j];
            if(j >= arr[i]) {
                g[j] -= g[j - arr[i]];
            }
        }
        b.reset();
        for(int j = 1; j <= sum; j++) {
            if(g[j])
                b.set(abs(sum - arr[i] - 2 * j));
        }
        a = a & b;
    }
    cout << a.count() << '\n';
    for(int i = 1; i <= sum; i++)
        if(a[i] == 1)
            cout << i << ' ';
}

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:12:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |         freopen("ESPORT.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
bootfall.cpp:13:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |         freopen("ESPORT.OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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