Submission #344970

#	Time	Username	Problem	Language	Result	Execution time	Memory
344970		_ani	Bootfall (IZhO17_bootfall)	C++17	13 / 100	520 ms	262148 KiB

bootfall

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 100;
vector<int> a, ans;
int SUM;
int dp[N + 1][N + 1][N * N + 1];
int hrashq[N + 1][N * N + 1];
int main()
{
	int n;
	cin >> n;
	a.resize(n);
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		SUM += a[i];
	}
	bool skzb = false;
	for (int jnj = 0; jnj < n; jnj++) {
		auto b = a;
		b.erase(b.begin() + jnj);
		for (int i = 0; i < n - 1; i++)
			for (int sum = 0; sum <= N * N; sum++) {
				if (i - 1 < 0)
					dp[jnj][i][0] = dp[jnj][i][b[i]] = 1;
				else {
					dp[jnj][i][sum] = max(dp[jnj][i][sum], dp[jnj][i - 1][sum]);
					if (sum - b[i] >= 0)
						dp[jnj][i][sum] = max(dp[jnj][i][sum], dp[jnj][i - 1][sum - b[i]]);
				}
				if (sum == SUM / 2 && dp[jnj][i][sum])skzb = true;
			}
	}
	if (SUM % 2)skzb = false;
	for (int i = 1; i <= N * N; i++)
	{
		bool ok = true;
		for (int jnj = 0; jnj < n; jnj++)
		{
			int cursum = i - a[jnj] + SUM;
			if (cursum % 2 || cursum > N * N) {
				ok = false;
				break;
			}
			bool lavalava = false;
			for (int k = 0; k < n - 1; k++)
				if (dp[jnj][k][cursum / 2] == 1)
					lavalava = true;
			if (!lavalava)ok = false;
		}
		if (ok && skzb)ans.push_back(i);
	}
	cout << ans.size() << '\n';
	for (int a : ans)
		cout << a << ' ';
	return 0;
}

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