Submission #498522

#	Time	Username	Problem	Language	Result	Execution time	Memory
498522		Bob	Bootfall (IZhO17_bootfall)	C++14	65 / 100	1040 ms	9808 KiB

bootfall

#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <array>
#include <set> 
#include <iomanip>
#include <queue>
#include <deque>

/*
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native") // Enable AVX/AVX2
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("unswitch-loops")
#pragma GCC optimize("fast-math")
#pragma GCC optimize("rename-registers") // Optimization flags
*/

using namespace std;

using ll = long long;
using db = double;



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

	
	ll n; cin >> n;
	ll p = 0;
	vector<ll> a(2 * n + 1000, 0);
	for (ll i = 1; i < n + 1; i++) {
		cin >> a[i];
		p += a[i];
	}

	vector<ll> dp(5e5, 0), ans(5e5, 0);
	dp[0] = 1;
	ans[0] = n + 1;
	for (ll i = 1; i < n + 1; i++) {
		for (ll j = p; j >= 0; j--)
			dp[j + a[i]] += dp[j];
	}


	vector<ll> res;
	for (ll i = 1; i <= n; i++) {
		p -= a[i];

		for (ll j = 0; j <= p; j++) {
			dp[j + a[i]] -= dp[j];
			
			ll x = max(j + j - p, 0ll);
			if (dp[j] != 0)
				ans[x]++;
			if (ans[x] == n)
				res.push_back(x);
		}
		for (ll j = p; j >= 0; j--)
			dp[j + a[i]] += dp[j];
		p += a[i];
	}

	if (dp[p / 2] == 0) {
		cout << 0; 
		return 0;
	}

	cout << res.size() << endl;
	for (ll x : res)
		cout << x << " ";


    return 0;
}

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