oj.uz

답안 #759747

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
759747 2023-06-16T18:21:37 Z NK_ Bootfall (IZhO17_bootfall) C++17
0 / 100
 1 ms 596 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

const int nax = 505;
const int kax = nax * nax;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N; cin >> N;
	vector<int> A(N); for(auto& x : A) cin >> x;

	bitset<kax> ans; ans.set();

	function<void(int, int, bitset<kax>&)> dnc = [&](int l, int r, bitset<kax>& dp) {
		cout << l << " " << r << endl;
		int m = (l + r) / 2;

		if (l > r) return;

		if (l == r) {
			dp <<= A[l];
			ans &= dp;
			return;
		}

		bitset<kax> ndp;
		// GO LEFT
		ndp = dp;
		for(int x = m + 1; x <= r; x++) ndp |= (ndp << 2*A[x]);
		dnc(l, m, ndp);

		// GO RIGHT
		ndp = dp;
		for(int x = l; x <= m; x++) ndp |= (ndp << 2*A[x]);
		dnc(m+1, r, ndp);
	};

	int S = accumulate(begin(A), end(A), 0);

	if (S % 2) {
		cout << 0 << nl;
		return 0;
	}

	bitset<kax> dp; dp[0] = 1;
	for(auto x : A) dp |= (dp << x);

	if (!dp[S / 2]) {
		cout << 0 << nl;
		return 0;
	}

	dp.reset(); dp[0] = 1;
	dnc(0, N - 1, dp);

	vector<int> ANS;
	for(int SUM = 0; SUM <= S; SUM++) if (ans[SUM]) ANS.push_back(S - SUM);
	reverse(begin(ANS), end(ANS));

	cout << size(ANS) << nl;
	for(auto x : ANS) cout << x << " ";
	cout << nl;

    return 0;
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -