Submission #167370

#	Time	Username	Problem	Language	Result	Execution time	Memory
167370		GioChkhaidze	Bootfall (IZhO17_bootfall)	C++14	100 / 100	705 ms	2772 KiB

bootfall

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=505;
int n,S,a[N],dp[N*N],mod=1e9+7;
vector < int > ans; 
bitset < N*N > A,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; j>=a[i]; j--) {
			dp[j]+=dp[j-a[i]];
			if (dp[j]>mod) dp[j]-=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;
		}
		
		S-=a[i];
		for (int j=1; j<=S; j++) {
			if (S<j) continue;
			if (!dp[j] && !dp[S-j]) continue;
 			A[abs(S-j-j)]=1;
		}
		S+=a[i];
		
		C=A&C,A=0;
	
		for (int j=S; j>=a[i]; j--) {
			dp[j]+=dp[j-a[i]];
			if (dp[j]>mod) dp[j]-=mod;
		}
	}

	for (int i=1; i<=S; i++)
		if (C[i]) ans.push_back(i);
 
 	printf("%d\n",ans.size());
 	
 	for (int i=0; i<ans.size(); i++)
 		printf("%d ",ans[i]);
}

Compilation message (stderr)

bootfall.cpp:8:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
bootfall.cpp: In function 'int main()':
bootfall.cpp:58:27: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
   printf("%d\n",ans.size());
                 ~~~~~~~~~~^
bootfall.cpp:60: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: 35 / 35