Submission #38272

#	Time	Username	Problem	Language	Result	Execution time	Memory
38272		Talant	Bootfall (IZhO17_bootfall)	C++14	100 / 100	269 ms	22400 KiB

bootfall

#include <bits/stdc++.h>

#define fr first
#define sc second
#define OK puts("OK");
#define pb push_back
#define mk make_pair

using namespace std;

typedef long long ll;

const ll inf = (ll)1e9 + 7;
const int N = (int)1e6 + 1;
const int M = (int)250001;

int n;
int a[N],sum;
int p[N],dp[N];
int cur[N];
int used[N];

vector <int> ans;

int main () {
        cin >> n;

        for (int i = 1; i <= n; i ++) {
                scanf ("%d", &a[i]);
                sum += a[i];
                p[i] = p[i - 1] + a[i];
        }

        if (sum & 1) {
                cout << 0;
                return 0;
        }
        dp[0] = 1;

        for (int i = 1; i <= n; i ++)
                for (int j = p[i]; j >= a[i]; j --)
                        dp[j] += dp[j - a[i]];

        if (!dp[sum / 2]) {
                cout << 0;
                return 0;
        }
        for (int i = 1; i <= sum; i ++)
                cur[i] = 1;

        for (int i = 1; i <= n; i ++) {
                if (used[a[i]])
                        continue;

                used[a[i]] = 1;
                sum -= a[i];

                for (int j = 0; j <= sum; j ++)
                        dp[j + a[i]] -= dp[j];

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

                sum += a[i];
        }
        for (int i = 1; i <= p[n]; i ++)
                if (cur[i] == 1)
                        ans.pb(i);

        cout << ans.size() << endl;

        for (int i = 0; i < ans.size(); i ++)
                cout << ans[i] << " ";
}

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:82:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < ans.size(); i ++)
                           ^
bootfall.cpp:29:36: 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