답안 #679674

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
679674	2023-01-08T21:50:47 Z	YENGOYAN	Bootfall (IZhO17_bootfall)	C++17	6 / 100	28 ms	2516 KB

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;
	int mx = 0;
	for (int i = 1; i <= n; ++i) {
		cin >> v[i];
		sm += v[i];
		mx = max(mx, 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>(mx * mx + 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] <= mx * mx; ++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 <= mx * mx; ++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

6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	4 ms	1260 KB	Output is correct
5	Correct	23 ms	2220 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	2 ms	524 KB	Output is correct
8	Correct	28 ms	2516 KB	Output is correct
9	Correct	4 ms	744 KB	Output is correct

Subtask #2

0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	4 ms	1260 KB	Output is correct
5	Correct	23 ms	2220 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	2 ms	524 KB	Output is correct
8	Correct	28 ms	2516 KB	Output is correct
9	Correct	4 ms	744 KB	Output is correct
10	Incorrect	2 ms	340 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #3

0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	4 ms	1260 KB	Output is correct
5	Correct	23 ms	2220 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	2 ms	524 KB	Output is correct
8	Correct	28 ms	2516 KB	Output is correct
9	Correct	4 ms	744 KB	Output is correct
10	Incorrect	2 ms	340 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #4

0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	4 ms	1260 KB	Output is correct
5	Correct	23 ms	2220 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	2 ms	524 KB	Output is correct
8	Correct	28 ms	2516 KB	Output is correct
9	Correct	4 ms	744 KB	Output is correct
10	Incorrect	2 ms	340 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #5

0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	4 ms	1260 KB	Output is correct
5	Correct	23 ms	2220 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	2 ms	524 KB	Output is correct
8	Correct	28 ms	2516 KB	Output is correct
9	Correct	4 ms	744 KB	Output is correct
10	Incorrect	2 ms	340 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #6

0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	4 ms	1260 KB	Output is correct
5	Correct	23 ms	2220 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	2 ms	524 KB	Output is correct
8	Correct	28 ms	2516 KB	Output is correct
9	Correct	4 ms	744 KB	Output is correct
10	Incorrect	2 ms	340 KB	Output isn't correct
11	Halted	0 ms	0 KB	-