Submission #93552

#	Time	Username	Problem	Language	Result	Execution time	Memory
93552		Turysbek	Bootfall (IZhO17_bootfall)	C++14	28 / 100	1072 ms	888 KiB

bootfall

// In the Name of God

#include <bits/stdc++.h>

using namespace std;

#define	ll long long
#define ull unsigned long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define sz(a) int(a.size())
#define all(v) v.begin(), v.end()
#define bpc(v) __builtin_popcountll(v)
#define itr iterator
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define per(i, a, b) for (int i = b; i >= a; --i)
#define ub upper_bound
#define lb lower_bound

const int N = 5e2 + 5;
const int mod = 1e8 + 7;
const int inf = 1e9 + 1;
const double eps = 1e-15;
const int pw = 257;

int n, a[N], sum, cnt[N * N];
bool dp[N * N];
vector<int> ans;

int main() {
	#ifdef Madi
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
	#endif

	ios_base :: sync_with_stdio(false); cin.tie(NULL);

    cin >> n;
    rep(i, 1, n) {
        cin >> a[i];
        sum += a[i];
    }

    if (sum % 2 == 1)
        return cout << 0, 0;

    dp[0] = 1;
    rep(i, 1, n)
        per(s, 1, sum / 2)
            if (s - a[i] >= 0)
                dp[s] |= dp[s - a[i]];

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

    rep(k, 1, n) {
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        rep(i, 1, n) {
            if (i == k)
                continue;
            per(s, 1, sum)
                if (s - a[i] >= 0)
                    dp[s] |= dp[s - a[i]];
        }
        rep(s, 1, sum)
            if (dp[s])
                ++cnt[max(0, s * 2 - (sum - a[k]))];
    }

    rep(x, 1, sum)
        if (cnt[x] == n)
            ans.pb(x);

    cout << sz(ans) << "\n";
    for (auto it : ans)
        cout << it << ' ';

	#ifdef Madi
    cerr << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    #endif
	return 0;
}

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