Submission #38790

#	Time	Username	Problem	Language	Result	Execution time	Memory
38790		DenXman111	Bootfall (IZhO17_bootfall)	C++14	13 / 100	83 ms	6088 KiB

bootfall

#include <iostream>
#include <queue>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <cstring>
#include <iomanip>
#include <set>
#include <sstream>
#include <ctime>

#define rust(a, b, c, d) sqrt(sqr(a - c) + sqr(b - d))

#define sqr(a) (a)*(a)
#define m_p make_pair
#define fi first
#define se second
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0)
#define endl '\n'

typedef long long ll;
const int MAXINT=2147483640;
const ll MAXLL=9223372036854775800LL;
const ll MAXN=250000;

using namespace std;

int dp[MAXN + 502], new_dp[MAXN + 502], a[MAXN];
int can[MAXN + 502];
vector <int> ans;

int main()
{
    fast_io;

    int n, sum = 0;

    cin >> n;
    for (int i = 1; i <= n; ++i) {cin >> a[i]; sum += a[i];}
    dp[0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = MAXN; j >= a[i]; --j) dp[j] += dp[j - a[i]];
    }
       if (sum % 2 || !dp[sum / 2]) return cout << 0, 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= MAXN; ++j) new_dp[j] += dp[j], new_dp[j + a[i]] -= new_dp[j];
        int new_sum = sum + a[i];
        for (int j = 0; j <= MAXN; ++j)
            if (sum - a[i] - j >= 0) if ((new_sum + j) % 2 == 0 && new_dp[(sum - a[i] - j) / 2]) ++can[j];
    }
    for (int i = 1; i <= MAXN; ++i) if (can[i] == n) ans.push_back(i);
    cout << ans.size() << endl; for (int i = 0; i < ans.size(); ++i) cout << ans[i] << " ";
    return 0;
}

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:54:51: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     cout << ans.size() << endl; for (int i = 0; i < ans.size(); ++i) cout << ans[i] << " ";
                                                   ^

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