Submission #501221

#	Time	Username	Problem	Language	Result	Execution time	Memory
501221		luka1234	Bootfall (IZhO17_bootfall)	C++14	100 / 100	616 ms	4444 KiB

bootfall

#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
using namespace std;
int dp[250001];
int d[250001];
int six[250001];
int main(){
	int n;
	cin>>n;
	int a[n+1];
	int sum=0;
	for(int k=1;k<=n;k++){
		cin>>a[k];
		sum+=a[k];
	}
	if(sum%2==1){
		cout<<0;
		return 0;
	}
	dp[0]=1;
	for(int i=1;i<=n;i++){
		for(int j=250000;j>=0;j--){
			if(j>=a[i])
			   dp[j]+=dp[j-a[i]];
		}
	}
	if(dp[sum/2]==0){
		cout<<0;
		return 0;
	}
	vector<int> ans;
	for(int i=1;i<=n;i++){
		for(int j=0;j<a[i];j++)
		    d[j]=dp[j];
		for(int j=a[i];j<=250000;j++){
			d[j]=dp[j]-d[j-a[i]];
		}
		for(int j=1;j<=250000;j++){
			if(d[j]==0)
			   continue;
			int x=2*j+a[i]-sum;
			if(x>0){
				six[x]++;
				if(six[x]==n)
				   ans.push_back(x);
			}
		}
	}
	sort(ans.begin(),ans.end());
	cout<<ans.size()<<"\n";
	for(int k=0;k<ans.size();k++)
	    cout<<ans[k]<<' ';
	return 0;
}

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:53:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |  for(int k=0;k<ans.size();k++)
      |              ~^~~~~~~~~~~

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