oj.uz

Submission #92742

# Submission time Handle Problem Language Result Execution time Memory
92742 2019-01-04T12:23:48 Z GioChkhaidze Bootfall (IZhO17_bootfall) C++14
6 / 100
 216 ms 476 KB 
#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

bootfall.cpp: In function 'int check(int)':
bootfall.cpp:19:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<a.size(); i++)
                ~^~~~~~~~~
bootfall.cpp:34:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int k=0; k<a.size(); k++)
                 ~^~~~~~~~~
bootfall.cpp: At global scope:
bootfall.cpp:54:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main ()
       ^
bootfall.cpp: In function 'int main()':
bootfall.cpp:71:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<ANS.size(); i++)
                ~^~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 14 ms 376 KB Output is correct
5 Correct 111 ms 476 KB Output is correct
6 Correct 3 ms 256 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 216 ms 376 KB Output is correct
9 Correct 20 ms 256 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 14 ms 376 KB Output is correct
5 Correct 111 ms 476 KB Output is correct
6 Correct 3 ms 256 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 216 ms 376 KB Output is correct
9 Correct 20 ms 256 KB Output is correct
10 Correct 44 ms 376 KB Output is correct
11 Correct 36 ms 256 KB Output is correct
12 Correct 19 ms 380 KB Output is correct
13 Correct 9 ms 256 KB Output is correct
14 Correct 45 ms 256 KB Output is correct
15 Correct 25 ms 256 KB Output is correct
16 Correct 35 ms 376 KB Output is correct
17 Correct 14 ms 344 KB Output is correct
18 Correct 29 ms 376 KB Output is correct
19 Incorrect 21 ms 256 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 14 ms 376 KB Output is correct
5 Correct 111 ms 476 KB Output is correct
6 Correct 3 ms 256 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 216 ms 376 KB Output is correct
9 Correct 20 ms 256 KB Output is correct
10 Correct 44 ms 376 KB Output is correct
11 Correct 36 ms 256 KB Output is correct
12 Correct 19 ms 380 KB Output is correct
13 Correct 9 ms 256 KB Output is correct
14 Correct 45 ms 256 KB Output is correct
15 Correct 25 ms 256 KB Output is correct
16 Correct 35 ms 376 KB Output is correct
17 Correct 14 ms 344 KB Output is correct
18 Correct 29 ms 376 KB Output is correct
19 Incorrect 21 ms 256 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 14 ms 376 KB Output is correct
5 Correct 111 ms 476 KB Output is correct
6 Correct 3 ms 256 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 216 ms 376 KB Output is correct
9 Correct 20 ms 256 KB Output is correct
10 Correct 44 ms 376 KB Output is correct
11 Correct 36 ms 256 KB Output is correct
12 Correct 19 ms 380 KB Output is correct
13 Correct 9 ms 256 KB Output is correct
14 Correct 45 ms 256 KB Output is correct
15 Correct 25 ms 256 KB Output is correct
16 Correct 35 ms 376 KB Output is correct
17 Correct 14 ms 344 KB Output is correct
18 Correct 29 ms 376 KB Output is correct
19 Incorrect 21 ms 256 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 14 ms 376 KB Output is correct
5 Correct 111 ms 476 KB Output is correct
6 Correct 3 ms 256 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 216 ms 376 KB Output is correct
9 Correct 20 ms 256 KB Output is correct
10 Correct 44 ms 376 KB Output is correct
11 Correct 36 ms 256 KB Output is correct
12 Correct 19 ms 380 KB Output is correct
13 Correct 9 ms 256 KB Output is correct
14 Correct 45 ms 256 KB Output is correct
15 Correct 25 ms 256 KB Output is correct
16 Correct 35 ms 376 KB Output is correct
17 Correct 14 ms 344 KB Output is correct
18 Correct 29 ms 376 KB Output is correct
19 Incorrect 21 ms 256 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 14 ms 376 KB Output is correct
5 Correct 111 ms 476 KB Output is correct
6 Correct 3 ms 256 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 216 ms 376 KB Output is correct
9 Correct 20 ms 256 KB Output is correct
10 Correct 44 ms 376 KB Output is correct
11 Correct 36 ms 256 KB Output is correct
12 Correct 19 ms 380 KB Output is correct
13 Correct 9 ms 256 KB Output is correct
14 Correct 45 ms 256 KB Output is correct
15 Correct 25 ms 256 KB Output is correct
16 Correct 35 ms 376 KB Output is correct
17 Correct 14 ms 344 KB Output is correct
18 Correct 29 ms 376 KB Output is correct
19 Incorrect 21 ms 256 KB Output isn't correct
20 Halted 0 ms 0 KB -