#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#include <cmath>
#include <stack>
#include <set>
#include <functional>
#include <bitset>
#include <map>
#include <unordered_map>
#include <queue>
#include <array>
#include <numeric>
#include <complex>
using namespace std;
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename A> ostream& operator<<(ostream &os, vector<A>&a) { for(auto &c:a)os<<c<<' '; return os;}
template<typename A> istream& operator>>(istream &os, vector<A>&a) { for(auto &c:a)os>>c; return os;}
template<typename A,size_t N> istream& operator>>(istream &os, array<A,N>&a) { for(auto &c:a)os>>c; return os;}
template<typename A,typename B> istream& operator>>(istream &os, pair<A,B>&a) { os>>a.first>>a.second; return os;}
#define bug(a) cerr << "(" << #a << ": " << a << ")\n";
#define all(x) x.begin(),x.end()
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define PQ priority_queue
using pii= pair<int,int>;
using VI= vector<int>;
using v64= vector<int64_t>;
using i64= int64_t;
using i16= int16_t;
using u64= uint64_t;
using u32= uint32_t;
using i32= int32_t;
using u16= uint16_t;
const i32 inf=1e9;
const i64 INF=1e18;
const int mod=1e9+7;
const int sigma=26;
string yn(bool x){if(x)return "YES";return "NO";}
typedef complex<double> point;
template<typename T>
void add(vector<T>&dp,const int& x)
{
for(int i=int(dp.size())-1;i>=x;i--)
{
dp[i]+=dp[i-x];
}
}
template<typename T>
void scot(vector<T>&dp,const int& x)
{
for(int i=x;i<=int(dp.size())-1;i++)
{
dp[i]-=dp[i-x];
}
}
const int N=500;
typedef bitset<N*N> bs;
//ifstream cin("bootfall.in");
//ofstream cout("bootfall.out");
void solve()
{
int n;
cin>>n;
vector<int>a(n);
cin>>a;
int sum=accumulate(all(a),0);
vector<u64>dp(sum+1,0);
dp[0]=1;
for(auto &c:a)
{
add(dp,c);
}
if(sum%2 || dp.back()==0)
{
cout<<0;
return;
}
bs sol;
for(int i=0;i<=N*N;i++)
{
sol[i].flip();
}
for(auto &c:a)
{
sum-=c;
scot(dp,c);
bs aux;
for(int i=0;i<=sum/2;i++)
{
if(dp[i])
{
aux[sum-2*i].flip();
}
}
sol&=aux;
add(dp,c);
sum+=c;
}
cout<<sol.count()<<'\n';
for(int i=0;i<=N*N;i++)
{
if(sol[i])
{
cout<<i<<' ';
}
}
}
main()
{
i32 tt=1;
ios::sync_with_stdio(false);
cin.tie(0);
//cin>>tt;
while(tt--)
{
solve();
}
}
Compilation message
bootfall.cpp:111:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
111 | main()
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
