Submission #93399

#	Time	Username	Problem	Language	Result	Execution time	Memory
93399		emil_physmath	Bootfall (IZhO17_bootfall)	C++17	44 / 100	56 ms	2268 KiB

bootfall

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
const int MAXN=275;
 
int a[MAXN], sum=0;
bool isAns[100000];
long long dp[100000];

void add(int);
void rem(int);
int main()
{
	int n, stSum;
	cin>>n;
	dp[0]=1;
	for (int i=0; i<n; i++)
	{
		cin>>a[i];
		add(a[i]);
	}
	stSum=sum;
	for (int i=0; i<=stSum; i++) isAns[i]=true;
	if (stSum%2 || dp[stSum/2]==0)
	{
		cout<<"0\n";
		return 0;
	}
	for (int i=0; i<n; i++)
	{
		rem(a[i]);
		for (int curAns=0; curAns<=stSum; curAns++)
			if ((sum+curAns)%2 || !dp[(sum+curAns)/2])
				isAns[curAns]=false;
		add(a[i]);
	}
	vector<int> ans;
	for (int x=1; x<=sum; x++)
		if (isAns[x])
			ans.push_back(x);
	cout<<ans.size()<<'\n';
	for (int i=0; i<ans.size(); i++)
		cout<<ans[i]<<' ';
	cout<<'\n';
 
	char I;
	cin >> I;
	return 0;
}

void add(int k)
{
	sum+=k;
	for (int j=sum; j>=0; j--)
		dp[j+k]+=dp[j];
}
 
void rem(int k)
{
	for (int i=0; i<=sum; i++)
		dp[i+k]-=dp[i];
	sum-=k;
}

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:45:17: 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: 0 / 21
• Subtask 6: 0 / 35