Submission #886977

#	Time	Username	Problem	Language	Result	Execution time	Memory
886977		NintsiChkhaidze	Bootfall (IZhO17_bootfall)	C++17	100 / 100	219 ms	2640 KiB

bootfall

#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
#define left (h<<1),l,(l + r)/2
#define right ((h<<1)|1),(l + r)/2 + 1,r
#define pii pair<int,int>
#define ll long long
using namespace std;

const int N = 500 + 5;

int a[N],n,sum;
bitset <250005> dp,ans;

void go(int l,int r){

	if (l == r){
		for (int x = 0; x <= 250000; x++){
			int newsum = sum - a[l] + x;
			if (!(newsum%2==0 && newsum/2 >= x && dp[newsum/2 - x]))
				ans[x] = 0;
		}
		return;
	}

	int mid = (l + r)>>1;
	//right child-shi gadavdivart

	bitset <250005> olddp = dp;
	for (int j = l; j <= mid; j++){
		dp |= (dp << a[j]);
	}
	go(mid + 1,r);

	//left child-shi gadavdivart
	dp = olddp;
	for (int j = mid + 1; j <= r; j++){
		dp |= (dp << a[j]);
	}
	go(l,mid);
	
	dp = olddp;
}
signed main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	
	cin>>n;
	dp[0] = 1;
	for (int i = 1; i <= n; i++){
		cin >> a[i];
		sum += a[i];
		dp |= (dp << a[i]);
	}
	
	if (sum & 1 || !dp[sum/2]){
		cout<<0;
		exit(0);
	}

	for (int j = 0; j <= 250000; j++)
		ans[j] = 1;
	
	dp = 0;
	dp[0] = 1;
	go(1,n);

	vector <int> res;
	for (int j = 0; j <= 250000; j++)
		if (ans[j]) res.pb(j);

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

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