Submission #549126

#	Time	Username	Problem	Language	Result	Execution time	Memory
549126		Pherokung	Bootfall (IZhO17_bootfall)	C++14	100 / 100	434 ms	3500 KiB

bootfall

#include<bits/stdc++.h>
using namespace std;
#define N 500*500 + 10
int n,a[505],sum=0,ans[N],num;
bitset<N> dp;
void sol(int be,int ed,bitset<N> now){
	if(be == ed){
		for(int i=1;i<=N;i++){
			if(!now[i] || (i <= sum - a[be] - i)) continue;
			ans[abs((sum - a[be] - i) - i)]++;
		}
		return;
	}
	int mid = (be+ed)/2;
	bitset<N> l = now, r = now;
	for(int i=be;i<=mid;i++) r |= r << a[i];
	for(int i=mid+1;i<=ed;i++) l |= l << a[i];
	sol(be,mid,l), sol(mid+1,ed,r);
}
int main(){
	scanf("%lld",&n);
	dp = 1;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]), dp |= dp << a[i], sum += a[i];
	if(sum % 2 || !dp[sum/2]){ printf("0"); return 0;} 
	dp = 1, sol(1,n,dp);
	for(int i=1;i<=N;i++) if(ans[i] == n) num++;
	printf("%d\n",num);
	for(int i=1;i<=N;i++) if(ans[i] == n) printf("%d ",i);
}

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:21:12: warning: format '%lld' expects argument of type 'long long int*', but argument 2 has type 'int*' [-Wformat=]
   21 |  scanf("%lld",&n);
      |         ~~~^  ~~
      |            |  |
      |            |  int*
      |            long long int*
      |         %d
bootfall.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |  scanf("%lld",&n);
      |  ~~~~~^~~~~~~~~~~
bootfall.cpp:23:29: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  for(int i=1;i<=n;i++) scanf("%d",&a[i]), dp |= dp << a[i], sum += a[i];
      |                        ~~~~~^~~~~~~~~~~~
bootfall.cpp:26:32: warning: iteration 250009 invokes undefined behavior [-Waggressive-loop-optimizations]
   26 |  for(int i=1;i<=N;i++) if(ans[i] == n) num++;
      |                           ~~~~~^
bootfall.cpp:26:15: note: within this loop
   26 |  for(int i=1;i<=N;i++) if(ans[i] == n) num++;
      |               ^
bootfall.cpp:28:32: warning: iteration 250009 invokes undefined behavior [-Waggressive-loop-optimizations]
   28 |  for(int i=1;i<=N;i++) if(ans[i] == n) printf("%d ",i);
      |                           ~~~~~^
bootfall.cpp:28:15: note: within this loop
   28 |  for(int i=1;i<=N;i++) if(ans[i] == n) printf("%d ",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