Submission #676151

#	Time	Username	Problem	Language	Result	Execution time	Memory
676151		HamletPetrosyan	Bootfall (IZhO17_bootfall)	C++17	13 / 100	21 ms	1324 KiB

bootfall

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int N = 1000, M = 122505;

ll n, a[N], sum = 0;
ll dp[N * N];
ll qn[N * N];

void solve(){
	cin >> n;
	for(int i = 0; i < n; i++) cin >> a[i], sum += a[i];
	if(sum % 2 == 1){
		cout << "0\n";
		return;
	}
	dp[0] = 1;
	for(int i = 0; i < n; i++){
		for(int j = M - a[i]; j >= 0; j--){
			dp[j + a[i]] += dp[j];
		}
	}
//	for(int i = 0; i <= M; i++) cout << dp[i] << " ";
//	cout << "\n";
	if(dp[sum / 2] == 0){
		cout << "0\n";
		return;
	}
	for(int i = 0; i < n; i++){
		sum -= a[i];
		for(int j = 0; j <= M - a[i]; j++){
			dp[j + a[i]] -= dp[j];
		}
//		cout << i << ": ";
//		for(int j = 0; j <= M; j++){
//			cout << dp[j] << " ";
//		}
//		cout << "\n";
		for(int j = 0, x; j <= M; j++){
			if(dp[j] > 0){
				x = abs(sum - j - j);
//				cout << j << " " << sum << " " << x << "\n";
				if(qn[x] == i) qn[x] = i + 1;
			}
		}
//		for(int j = 0; j <= M; j++){
//			cout << qn[j] << " ";
//		}
//		cout << "\n";
		sum += a[i];
		for(int j = M - a[i]; j >= 0; j--){
			dp[j + a[i]] += dp[j];
		}
	}
	ll cnt = 0;
	for(int i = 1; i <= M; i++){
		if(qn[i] == n) cnt++;
	}
	cout << cnt << "\n";
	for(int i = 1; i <= M; i++){
		if(qn[i] == n) cout << i << " ";
	}
	cout << "\n";
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	solve();
	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