Submission #167369

#	Time	Username	Problem	Language	Result	Execution time	Memory
167369		GioChkhaidze	Bootfall (IZhO17_bootfall)	C++14	65 / 100	1067 ms	3536 KiB

bootfall

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=505;
int n,S,a[N];
ll dp[N*N],mod=1e9+7;
vector < int > ans; 
bitset < N*N > A,B,C;
main () {
	cin>>n;
	
	for (int i=1; i<=n; i++) {
		cin>>a[i];
		S+=a[i];
	}
	
	sort(a+1,a+n+1);
	
	dp[0]=1;
	for (int i=1; i<=n; i++)
		for (int j=S-a[i]; j>=0; j--) {
			dp[j+a[i]]+=dp[j];
			if (dp[j+a[i]]>mod) dp[j+a[i]]-=mod;
		}
 
	if (S%2 || !dp[S/2]) {
		cout<<0<<endl;
		return 0;
	}
	
	for (int i=1; i<=S; i++)
		C[i]=1;
	
	for (int i=1; i<=n; i++) {
		for (int j=a[i]; j<=S; j++) {
			dp[j]-=dp[j-a[i]];
			if (dp[j]<0) dp[j]+=mod;
		}

		for (int j=1; j<=S; j++) {
			int X=j,Y=S-a[i]-j;
			if (Y<0) continue;
			if (!dp[X] && !dp[Y]) continue;
 			A[abs(X-Y)]=1;
		}
		
		C=A&C;
		
		for (int j=1; j<=S; j++) 
			A[j]=0;
		
		for (int j=S-a[i]; j>=0; j--) {
			dp[j+a[i]]+=dp[j];
			if (dp[j+a[i]]>mod) dp[j+a[i]]-=mod;
		}
	}

	for (int i=1; i<=S; i++)
		if (C[i]) ans.push_back(i);
 
 	cout<<ans.size()<<endl;
 	
 	for (int i=0; i<ans.size(); i++)
 		cout<<ans[i]<<" ";
}

Compilation message (stderr)

bootfall.cpp:9:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
bootfall.cpp: In function 'int main()':
bootfall.cpp:63:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<ans.size(); i++)
                 ~^~~~~~~~~~~

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