Submission #136576

#	Time	Username	Problem	Language	Result	Execution time	Memory
136576		FedericoS	Bootfall (IZhO17_bootfall)	C++14	100 / 100	472 ms	2876 KiB

bootfall

#include <iostream>
#include <vector>
using namespace std;

int N,S;
int A[502];
int DP[260006];
vector<int> V;
bool flag[260006];

int main(){
	cin>>N;
	for(int i=0;i<N;i++){
		cin>>A[i];
		S+=A[i];
	}

	DP[0]=1;
	for(int i=0;i<N;i++)
		for(int j=S;j>=0;j--)
			if(j-A[i]>=0)
				DP[j]+=DP[j-A[i]];

	for(int j=0;j<N;j++){
		for(int k=A[j];k<=S;k++)
			DP[k]-=DP[k-A[j]];
		for(int i=1;i<S+1;i++){
			int k=(S+i-A[j])/2;
			if((S+i-A[j])%2==1 or !DP[k])
				flag[i]=true;
		}
		for(int k=S;k>=A[j];k--)
			DP[k]+=DP[k-A[j]];
	}

	for(int j=1;j<=S;j++)
		if(!flag[j])
			V.push_back(j);

	if(S%2 or !DP[S/2])
		V.clear();

	cout<<V.size()<<"\n";
	for(int x:V)
		cout<<x<<" ";

}

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