Submission #480595

#TimeUsernameProblemLanguageResultExecution timeMemory
480595pure_memBootfall (IZhO17_bootfall)C++14
100 / 100
128 ms4132 KiB
#pragma GCC optimize ("Ofast")
// #pragma GCC target ("avx2")

#include <iostream>
#include <bitset>
#include <vector>

#define X first
#define Y second
#define ll long long 
#define MP make_pair

using namespace std;

const int N = 500;
const ll mod = 1e9 + 7;

typedef bitset<N * N + 1> DP;

int n, sum, w[N];
int ans[N * N + 1];
DP cur;

void rec(int l, int r, DP cur) {
	if(r - l == 1) {
		for(int i = 0, j = sum - w[l];i <= j;i++, j--) {
			if(cur[i]) ans[j - i] += 1;
		} 
	}
	else {
		DP L = cur, R = cur;
		int m = (l + r) / 2;
		for(int i = l;i < r;i++) {
			if(i >= m) 
				R |= R << w[i];
			else 
				L |= L << w[i];
		}
		rec(l, m, R), rec(m, r, L);
	}
}

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

	cin >> n;
	for(int i = 0;i < n;i++)
		cin >> w[i], sum += w[i];
	
	DP cur = 1;
	for(int i = 0;i < n;i++)
		cur |= cur << w[i];
	if(cur[sum / 2] == 0) return cout << "0", 0;
	rec(0, n, DP(1));

	vector< int > res;
	for(int i = 0;i < N * N + 1;i++)
		if(ans[i] == n)
			res.push_back(i);
	
	cout << res.size() << "\n";
	for(int i: res)
		cout << i << " ";
	
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...