Submission #856374

#	Time	Username	Problem	Language	Result	Execution time	Memory
856374		hgglmao	Bootfall (IZhO17_bootfall)	C++17	100 / 100	288 ms	3156 KiB

bootfall

#include <bits/stdc++.h>
#define TASK "bootfall"

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ll> ill;
typedef pair<ll, int> lli;
typedef pair<ll, ll> pll;

const int MAX = 501;
const int SQMAX = 250001;

int n, a[MAX];
int sum;
ll dp[SQMAX];
bool check[SQMAX];

int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);

        if (fopen(TASK ".inp", "r"))
        {
                freopen(TASK ".inp", "r", stdin);
                freopen(TASK ".out", "w", stdout);
        }

        cin >> n;
        for (int i = 1; i <= n; ++i)
                cin >> a[i];

        sum = accumulate(a + 1, a + n + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= n; ++i)
                for (int j = sum - a[i]; j >= 0; --j)
                        dp[j + a[i]] += dp[j];

        if (sum % 2 || !dp[sum / 2])
                return cout << 0, 0;

        fill(check + 1, check + sum + 1, 1);
        for (int i = 1; i <= n; ++i)
        {
                for (int j = 0; j <= sum - a[i]; ++j)
                        dp[j + a[i]] -= dp[j];
                for (int cur = 1; cur <= sum; ++cur)
                {
                        if ((sum - a[i] + cur) % 2)
                        {
                                check[cur] = 0;
                                continue;
                        }
                        int cur_req = (sum - a[i] + cur) / 2;
                        if (cur_req <= sum && dp[cur_req])
                                continue;
                        // if (cur_req - cur >= 0 && cur_req - cur <= sum && dp[cur_req - cur])
                        //         continue;
                        check[cur] = 0;
                }
                for (int j = sum - a[i]; j >= 0; --j)
                        dp[j + a[i]] += dp[j];
        }

        cout << accumulate(check, check + sum + 1, 0) << '\n';
        for (int i = 0; i <= sum; ++i)
                if (check[i])
                        cout << i << ' ';
}

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:28:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |                 freopen(TASK ".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bootfall.cpp:29:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |                 freopen(TASK ".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