Submission #299100

#	Time	Username	Problem	Language	Result	Execution time	Memory
299100		TadijaSebez	Bootfall (IZhO17_bootfall)	C++11	100 / 100	231 ms	19440 KiB

bootfall

#include <bits/stdc++.h>
using namespace std;
const int N=505;
int n,a[N];
bitset<N*N> ans[N];
void DNC(int l,int r,bitset<N*N> now){
	if(l==r)ans[l]=now;
	else{
		int mid=l+r>>1;
		bitset<N*N> tmp=now;
		for(int i=l;i<=mid;i++)tmp|=tmp<<a[i];
		DNC(mid+1,r,tmp);
		tmp=now;
		for(int i=mid+1;i<=r;i++)tmp|=tmp<<a[i];
		DNC(l,mid,tmp);
	}
}
bitset<N*N> DP(int skip){
	return ans[skip];
	/*bitset<N*N> ans;
	ans[0]=1;
	for(int i=1;i<=n;i++)if(i!=skip)ans|=ans<<a[i];
	return ans;*/
}
int ok[N*N];
int main(){
	scanf("%i",&n);
	int sum=0;
	for(int i=1;i<=n;i++)scanf("%i",&a[i]),sum+=a[i];
	bitset<N*N> e;e[0]=1;
	DNC(0,n,e);
	bitset<N*N> all=DP(0);
	if(sum&1||!all[sum/2])return 0*printf("0\n");
	for(int i=1;i<=n;i++){
		bitset<N*N> dp=DP(i);
		for(int j=1;j<=sum;j++){
			if((sum-a[i]+j)%2==0&&dp[(sum-a[i]+j)/2])
				ok[j]++;
		}
	}
	vector<int> ans;
	for(int i=1;i<=sum;i++)if(ok[i]==n)ans.push_back(i);
	printf("%i\n",ans.size());
	for(int i:ans)printf("%i ",i);
	printf("\n");
	return 0;
}

Compilation message (stderr)

bootfall.cpp: In function 'void DNC(int, int, std::bitset<255025>)':
bootfall.cpp:9:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    9 |   int mid=l+r>>1;
      |           ~^~
bootfall.cpp: In function 'int main()':
bootfall.cpp:43:11: warning: format '%i' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   43 |  printf("%i\n",ans.size());
      |          ~^    ~~~~~~~~~~
      |           |            |
      |           int          std::vector<int>::size_type {aka long unsigned int}
      |          %li
bootfall.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |  scanf("%i",&n);
      |  ~~~~~^~~~~~~~~
bootfall.cpp:29:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   29 |  for(int i=1;i<=n;i++)scanf("%i",&a[i]),sum+=a[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