Submission #679673

#	Time	Username	Problem	Language	Result	Execution time	Memory
679673		YENGOYAN	Bootfall (IZhO17_bootfall)	C++17	0 / 100	1 ms	212 KiB

bootfall

/*
	//\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\\
	\\                                    //
	//  271828___182845__904523__53602__  \\
	\\  87___47____13______52____66__24_  //
	//  97___75____72______47____09___36  \\
	\\  999595_____74______96____69___67  //
	//  62___77____24______07____66__30_  \\
	\\  35___35____47______59____45713__  //
	//                                    \\
	\\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\//
												*/

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <climits>
#include <algorithm>
#include <random>
#include <queue>
#include <deque>
#include <iomanip>
#include <string>
#include <tuple>
#include <bitset>
#include <chrono>
#include <ctime>
#include <fstream>
#include <stack>
#include <cstdio>

using namespace std;
using ll = long long;
const int N = 3e5 + 5;
const ll mod = 1e9 + 7, inf = 1e12;

void solve() {
	// start time - 1:05
	int n; cin >> n;
	vector<int> v(n + 1);
	int sm = 0;
	for (int i = 1; i <= n; ++i) {
		cin >> v[i];
		sm += v[i];
	}
	map<int, int> mp;
	for (int ii = 0; ii <= n; ++ii) {
		int cur = sm - v[ii];
		vector<vector<int>> dp(n + 1, vector<int>(n * n + 5));
		dp[0][0] = 1;
		for (int i = 1; i <= n; ++i) {
			dp[i] = dp[i - 1];
			if (i == ii) continue;
			vector<int> dp_ = dp[i];
			for (int j = 0; j + v[i] <= n * n; ++j) {
				dp_[j + v[i]] |= dp[i][j];
				//if (!ii && i == 1 && j + v[i] == 1 && dp[i][j]) cout << "A\n";
			}
			dp[i] = dp_;
			//if(!ii) cout << dp[1][1] << "\n";
			// 1 3 1 5
		}
		for (int j = 1; j <= n * n; ++j) {
			if (!ii && (cur % 2 || !dp[n][cur / 2])) {
				//cout << dp[1][1] << "\n";
				cout << "0\n";
				return;
			}
			if (ii) {
				if ((cur + j) % 2) continue;
				if (dp[n][(cur + j) / 2]) ++mp[j];

			}
		}
	}
	int c = 0;
	for (pair<int, int> x : mp) {
		if (x.second == n) ++c;
	}
	//cout << mp[3] << "\n";
	cout << c << "\n";
	for (pair<int, int> x : mp) {
		if (x.second == n) cout << x.first << " ";
	}
}
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	//int t; cin >> t;
	//while (t--)
		solve();
}

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