Submission #480595

#	Time	Username	Problem	Language	Result	Execution time	Memory
480595		pure_mem	Bootfall (IZhO17_bootfall)	C++14	100 / 100	128 ms	4132 KiB

bootfall

#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;
}

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