Submission #1077063

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077063		xnqs	Bootfall (IZhO17_bootfall)	C++17	100 / 100	141 ms	3040 KiB

bootfall

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <cstdint>

int x;
int arr[505];
uint32_t knapsack[125005];
int freq[250005];

void knapsack_add(int val) {
	for (int i = 125004; i >= val; i--) {
		knapsack[i] += knapsack[i-val];
	}
}

void knapsack_remove(int val) {
	for (int i = 0; i < 125005-val; i++) {
		knapsack[i+val] -= knapsack[i];
	}
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> x;

	int sum = 0;
	knapsack[0] = 1;
	for (int i = 1; i <= x; i++) {
		std::cin >> arr[i];
		sum += arr[i];
		knapsack_add(arr[i]);
	}

#if 0
	for (int i = 0; i <= sum; i++) {
		std::cout << knapsack[i] << " ";
	}
	std::cout << "\n";
#endif

	if (sum%2==1) {
		std::cout << "0\n";
		return 0;
	}
	if (!knapsack[sum/2]) {
		std::cout << "0\n";
		return 0;
	}

	for (int i = x; i >= 1; i--) {
		sum -= arr[i];
		knapsack_remove(arr[i]);
		if (i+1<=x) {
			sum += arr[i+1];
			knapsack_add(arr[i+1]);
		}

		for (int i = 0; i <= sum/2; i++) {
			freq[sum-i-i] += !!knapsack[i];
		}

#if 0
		for (int i = 0; i <= sum; i++) {
			std::cout << knapsack[i] << " ";
		}
		std::cout << "\n";
#endif
	}

	std::vector<int> ret;
	for (int i = 1; i < 250005; i++) {
#if 0
		if (i<=10) {
			std::cout << i << " " << freq[i] << "\n";
		}
#endif
		if (freq[i]==x) {
			ret.emplace_back(i);
		}
	}

	std::cout << ret.size() << "\n";
	for (const auto& i : ret) {
		std::cout << i << " ";
	}
	std::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