Submission #93402

#	Time	Username	Problem	Language	Result	Execution time	Memory
93402		emil_physmath	Bootfall (IZhO17_bootfall)	C++17	100 / 100	343 ms	4204 KiB

bootfall

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

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

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

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:45:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (long long 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