Submission #171235

#	Time	Username	Problem	Language	Result	Execution time	Memory
171235		Lightning	Bootfall (IZhO17_bootfall)	C++14	100 / 100	407 ms	2932 KiB

bootfall

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <iomanip>
#include <stack>
#include <queue>
#include <deque>

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define pb push_back
#define ppb pop_back
#define mkp make_pair
#define F first
#define S second
#define show(a) cerr << #a <<" -> "<< a <<"\n"
#define fo(a, b, c, d) for(int (a) = (b); (a) <= (c); (a) += (d))
#define foo(a, b, c ,d) for(int (a) = (b); (a) >= (c); (a) -= (d))
//#define int ll

const int N = 505;
const int Tima = (500 * 500) + 5;

int n, sum, dp[Tima], a[N];
bool can[Tima];
vector <int> ans;

void add(int x) {
	sum += x;
	for(int i = sum; i >= x; --i) {
		dp[i] += dp[i - x];
	}
}

void del(int x) {
	for(int i = x; i <= sum; ++i) {
		dp[i] -= dp[i - x];
	}
	sum -= x;
}

int main () {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	dp[0] = 1;
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i];
		add(a[i]);
	}
	if((sum % 2 == 1) || (dp[sum / 2] == 0)) {
		puts("0");
		return 0;
	}
	for(int i = 0; i < Tima; ++i) 
		can[i] = true;
	for(int i = 1; i <= n; ++i) {
		del(a[i]);
		for(int x = 0; x < Tima; ++x) {
			if(((sum + x) % 2 == 1) || (dp[(sum + x) / 2] == 0)) {
				can[x] = 0;
			}
		}
		add(a[i]);
	}
	for(int i = 0; i < Tima; ++i) {
		if(can[i])
			ans.pb(i);
	}
	cout << sz(ans) <<'\n';
	for(int it : ans)
		cout << it <<' ';
	return 0;
}
/*
	If you only do what you can do, 
	You will never be more than you are now!

	
	We must all suffer from one of two pains: the pain of discipline or the pain of regret. 
	The difference is discipline weighs grams while regret weighs tons.
*/

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