Submission #1152536

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152536		hamzabc	Bootfall (IZhO17_bootfall)	C++20	28 / 100	1066 ms	4800 KiB

bootfall

#include <bits/stdc++.h>
 

using namespace std;
 
 
#define all(x) x.begin(), x.end()
#define mod 1000000007
#define sp << " " <<
#define endl << '\n'
vector<long long int> lst;
vector<long long int> sumplane;


signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	long long int N, sumall = 0;
	cin >> N;
	lst.resize(N);
	sumplane.resize(500 * N);
	for (int i = 0; i < N; i++){
		cin >> lst[i];
		sumall += lst[i];
	}
	sumplane[0] = 1;
	for (int o = 0; o < N; o++){
		for (int i = N * 500 - lst[o]; i >= 0; i--){
			if (sumplane[i]){
				sumplane[i + lst[o]] += sumplane[i];
			}
		}
	}
	if (sumall % 2 || sumplane[sumall / 2] == 0){
		cout << 0;
		return 0;
	}
	set<long long int> ret, newret;
	vector<long long int> check(N * 500);
	for (int o = 0; o < N; o++){
		fill(all(check), 0);
		for (int i = 500 * N - 1; i >= (sumall + lst[o] + 1) / 2; i--){
			if (check[i] == sumplane[i]){
				check[i] = 0;
				continue;
			}
			check[i - lst[o]] += sumplane[i] - check[i];
			check[i] = 1;
		}
		for (int i = (sumall + lst[o] + 1) / 2; i < N * 500; i++){
			if (o){
				if (check[i]){
					if (ret.find(2 * i - sumall - lst[o]) != ret.end())
						newret.insert(2 * i - sumall - lst[o]);
				}
			}else{
				if (check[i]){
					newret.insert(2 * i - sumall - lst[0]);
				}
			}
		}
		ret.swap(newret);
		newret.clear();
	}
	cout << ret.size() endl;
	for (auto k : ret)
		cout << k sp "";
}

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