# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
92742 | GioChkhaidze | Bootfall (IZhO17_bootfall) | C++14 | 216 ms | 476 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define F first
#define S second
#define Pb push_back
using namespace std;
int n,k[100005],X,Ans,x,su;
vector < int > ANS,a;
inline int check(int x)
{
int Sum=0;
a.Pb(x);
for (int i=0; i<a.size(); i++)
Sum+=a[i];
for (int i=a.size()-1; i>=max(0,int(a.size())-20); i--)
{
int X=a[i],ko=0;
a[i]=0;
int dp[100005];
for (int j=0; j<=2*su; j++)
dp[j]=0;
dp[0]=1;
for (int k=0; k<a.size(); k++)
for (int j=2*su; j>=0; j--)
if (0<=j-a[k] && dp[j-a[k]]) dp[j]=1;
if ((Sum-X)%2==1 || !dp[(Sum-X)/2]) ko=1;
a[i]=X;
if (ko)
{
a.pop_back();
return 0;
}
}
a.pop_back();
return 1;
}
main ()
{
cin>>n;
for (int i=1; i<=n; i++)
{
cin>>x;
a.Pb(x);
su+=x;
}
for (int i=1; i<=su; i++)
if (check(i)) ANS.Pb(i);
cout<<ANS.size()<<endl;
for (int i=0; i<ANS.size(); i++)
cout<<ANS[i]<<" ";
}
/*
4
1 3 1 5
6
3 5 7 11 9 13
3
2 2 2
4
200 200 200 200
*/
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |