Submission #514767

#	Time	Username	Problem	Language	Result	Execution time	Memory
514767		ymm	Bootfall (IZhO17_bootfall)	C++17	100 / 100	217 ms	17832 KiB

bootfall

///
///   What would happen if we used assembly language for CP?
///   Sorry, that was a strange thing to ask.
///

#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
#define LoopR(x,l,r) for(ll x = ll(r)-1; x >= ll(l); --x)
#define Kill(x) exit((cout << (x) << '\n', 0))
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
using namespace std;

const int N = 505;
int a[N];
bitset<N*N> bs[N];
int n;
int sum=0;

vector<int> t[N<<2];
bitset<N*N> dc[11]; int dcc=0;
void add(int l, int r, int x, int i=0, int b=0, int e=N){
	if(r<=b||e<=l||l>=r) return;
	if(l<=b&&e<=r) {t[i].push_back(x); return;}
	add(l,r,x,2*i+1,b,(b+e)/2);
	add(l,r,x,2*i+2,(b+e)/2,e);
}
void push(int i){
	dc[dcc+1] = dc[dcc];
	++dcc;
	for(int x : t[i]) dc[dcc] = dc[dcc]|(dc[dcc]<<x);
}
void dfs(int i=0, int b=0, int e=N){
	push(i);
	if(e-b==1){bs[b]=dc[dcc];--dcc;return;}
	dfs(2*i+1,b,(b+e)/2);
	dfs(2*i+2,(b+e)/2,e);
	--dcc;
}

bool test(int x){
	Loop(i,0,n){
		if(sum-a[i]-x<0) return 0;
		if((sum-a[i]-x)&1) return 0;
		if(!bs[i][(sum-a[i]-x)/2]) return 0;
	}
	return 1;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n;
	Loop(i,0,n){
		cin >> a[i];
		add(0,i,a[i]);
		add(i+1,n+1,a[i]);
		sum += a[i];
	}
	dc[0][0]=1;
	dfs();
	//Loop(i,0,n+1) {Loop(j,0,50) cout<<bs[i][j]; cout << '\n';}
	if((sum&1) || !bs[n][sum/2]) Kill("0\n");
	vector<int> ans;
	Loop(i,0,N*N) if(test(i)) ans.push_back(i);
	cout << ans.size() << '\n';
	for(int x : ans) cout << x << ' ';
	cout << '\n';
}

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