Submission #38264

#	Time	Username	Problem	Language	Result	Execution time	Memory
38264		Talant	Bootfall (IZhO17_bootfall)	C++14	28 / 100	1000 ms	83428 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)72901;

int n;
int dp[271][72905];
int a[N],sum;
vector <int> ans;

int main () {
        cin >> n;

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

        int g = (a[1] % 2);

        for (int i = 1; i <= n; i ++) {
                if (a[i] % 2 != g) {
                        cout << "0";
                        return 0;
                }
        }


        for (int i = 0; i <= n; i ++)
                memset(dp[i],-1,sizeof(dp[i]));

        for (int i = 0; i <= n; i ++) {
                dp[i][0] = 1;
                vector <int> v;
                v.pb(0);
                for (int j = 1; j <= n; j ++) {
                        if (j == i)
                                continue;
                        int o = (int) v.size();
                        for (int k = 0; k < o; k ++) {
                                if (sum >= v[k] + a[j] && dp[i][v[k] + a[j]] == -1) {
                                        dp[i][v[k] + a[j]] = 1;
                                        v.pb(v[k] + a[j]);
                                }
                        }
                }
                if (sum % 2 != 0 || dp[0][sum / 2] == -1) {
                        cout << "0";
                        return 0;
                }
        }

        if (g == 0)
                g = 2;

        for (int i = g; i <= sum; i += 2) {
                int f = 0;
                if (sum % 2 != 0 || dp[0][sum / 2] == -1)
                        continue;

                for (int j = 1; j <= n; j ++) {
                        if ((sum - a[j] + i) % 2 != 0 || (sum - a[j] + i) / 2 - i < 0 || dp[j][(sum - a[j] + i) / 2 - i] == -1 || dp[j][(sum - a[j] + i) / 2] == -1) {
                                f = 1;
                                break;
                        }
                }
                if (!f)
                        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:81:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < ans.size(); i ++)
                           ^

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