제출 #906880

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
906880		daoquanglinh2007	Bootfall (IZhO17_bootfall)	C++17	65 / 100	449 ms	3156 KiB

bootfall

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

const int NM = 500, MOD = 1e9+321;

int N, a[NM+5], sum = 0, dp[NM*NM+5], dp0[NM*NM+5], K = 0;
bool ok[NM*NM+5];

void add(int x){
	for (int i = NM*NM; i >= x; i--)
		dp[i] = (dp[i]+dp[i-x])%MOD;
}

void remove(int x){
	for (int i = x; i <= NM*NM; i++)
		dp[i] = (dp[i]+MOD-dp[i-x])%MOD;
}

void solve(int t){
	for (int i = 0; i <= NM*NM; i++) dp[i] = dp0[i];
	remove(a[t]);
	
	for (int i = 1; i <= NM*NM; i++)
		if ((sum-a[t]+i)%2 != 0 || (sum-a[t]+i)/2-i < 0 || !dp[(sum-a[t]+i)/2-i]) ok[i] = 0;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> N;
	dp[0] = 1;
	for (int i = 1; i <= N; i++){
		cin >> a[i];
		sum += a[i];
		add(a[i]);
	}
	if (sum%2 != 0 || !dp[sum/2]){
		cout << "0\n";
		return 0;
	}
	for (int i = 0; i <= NM*NM; i++){
		dp0[i] = dp[i];
		ok[i] = 1;
	}
	for (int i = 1; i <= N; i++)
		solve(i);
		
	for (int i = 1; i <= NM*NM; i++) K += ok[i];
	
	cout << K << '\n';
	for (int i = 1; i <= NM*NM; i++)
		if (ok[i]) cout << i << ' ';
		
	return 0;
}

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