Submission #683813

#	Time	Username	Problem	Language	Result	Execution time	Memory
683813		HamletPetrosyan	Bootfall (IZhO17_bootfall)	C++17	100 / 100	297 ms	4828 KiB

bootfall

/// -- -- ---- --- -- --
/// 19.01.2023 Thu 15:53
/// -- -- ---- --- -- --

#include <bits/stdc++.h>
using namespace std;

#define pll pair<long long, long long>
#define all(a) (a).begin(), (a).end()
#define len(a) ((int)(a).size())
#define add push_back
#define mkp make_pair
#define ll long long
#define fr first
#define sc second

const long long INF = 1000000000ll * 1000000003ll;
const long long MOD = 1000000007ll;
const int N = 5e2 + 5;

ll n, a[N];
ll cnt[N * N];
ll ans[4 * N * N];
ll sum = 0;

void solve(){
	cin >> n;
	for(int i = 0; i < n; i++) cin >> a[i];
	cnt[0] = 1;
	for(int i = 0; i < n; i++){
		sum += a[i];
		for(int j = 250000 - a[i]; j >= 0; j--){
			cnt[j + a[i]] += cnt[j];
		}
	}
	if(sum % 2 == 1 || !cnt[sum / 2]){
		cout << "0\n";
		return;
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j <= 250000; j++){
			if(cnt[j] && j * 2 >= sum - a[i]) ans[j * 2 - sum + a[i]]++;
			if(j <= 250000 - a[i]) cnt[j + a[i]] -= cnt[j];
		}
		for(int j = 250000 - a[i]; j >= 0; j--) cnt[j + a[i]] += cnt[j];
	}
	ll num = 0;
	for(int i = 1; i <= 500000; i++){
		if(ans[i] == n) num++;
	}
	cout << num << "\n";
	for(int i = 1; i <= 500000; i++){
		if(ans[i] == n) cout << i << " ";
	}
	cout << "\n";
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	int _ = 1;
	// cout << fixed;
	// cout.precision(9);

	// cin >> _ ;
	while(_--) solve();
	return 0;
}

/// ---- - --------  ------ -------- -- - - -
/// just a reminder. ubuntu password is i o 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