oj.uz

Submission #93073

# Submission time Handle Problem Language Result Execution time Memory
93073 2019-01-06T11:34:52 Z emil_physmath Bootfall (IZhO17_bootfall) C++17
28 / 100
 736 ms 5460 KB 
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <vector>
using namespace std;
const int MAXN=505;

int a[MAXN];
bool isNotAns[501*501];

vector<int> NotPossSums(int arr[], int n);
int main()
{
	int n, sum=0;
	cin>>n;
	for (int i=0; i<n; i++)
	{
		cin>>a[i];
		sum+=a[i];
	}
	vector<int> temp=NotPossSums(a, n);
	auto it=lower_bound(temp.begin(), temp.end(), sum/2);
	if (sum%2 || (it!=temp.end() && *it==sum/2)) {
		cout<<"0\n";
		return 0;
	}
	for (int j=0; j<n; j++)
	{
		swap(a[j], a[n-1]);
		vector<int> temp=NotPossSums(a, n-1);
		swap(a[j], a[n-1]);
		for (int x=1; x<=sum; x++)
			if ((sum-a[j]+x)%2 || (sum-a[j]+x)/2-x<0)
				isNotAns[x]=true;
		for (int i=0; i<temp.size(); i++)
		{
			int cur=temp[i];
			if (sum-a[j]-2*cur>0) isNotAns[sum-a[j]-2*cur]=true;
		}
	}
	vector<int> ans;
	for (int x=1; x<=sum; x++)
		if (!isNotAns[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;
}

bool dp[MAXN][10000];
vector<int> NotPossSums(int arr[], int n)
{
	int sum=0;
	for (int i=0; i<n; i++)
		sum+=arr[i];
	memset(dp, 0, sizeof(dp));
	for (int i=0; i<=n; i++)
		dp[i][0]=true;
	for (int i=1; i<=n; i++)
	{
		dp[i][arr[i-1]]=true;
		for (int j=1; j<=sum; j++)
		{
			if (dp[i-1][j]==true)
			{
				dp[i][j]=true;
				dp[i][j+arr[i-1]]=true;
			}
		}
	}
	vector<int> res;
	for (int j=0; j<=sum; j++)
		if (!dp[n][j])
			res.push_back(j);
	return res;
}

Compilation message

bootfall.cpp: In function 'int main()':
bootfall.cpp:38:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<temp.size(); i++)
                 ~^~~~~~~~~~~~
bootfall.cpp:49: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 6 ms 5240 KB Output is correct
2 Correct 9 ms 5240 KB Output is correct
3 Correct 5 ms 5240 KB Output is correct
4 Correct 6 ms 5244 KB Output is correct
5 Correct 8 ms 5240 KB Output is correct
6 Correct 7 ms 5240 KB Output is correct
7 Correct 6 ms 5240 KB Output is correct
8 Correct 8 ms 5240 KB Output is correct
9 Correct 8 ms 5240 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5240 KB Output is correct
2 Correct 9 ms 5240 KB Output is correct
3 Correct 5 ms 5240 KB Output is correct
4 Correct 6 ms 5244 KB Output is correct
5 Correct 8 ms 5240 KB Output is correct
6 Correct 7 ms 5240 KB Output is correct
7 Correct 6 ms 5240 KB Output is correct
8 Correct 8 ms 5240 KB Output is correct
9 Correct 8 ms 5240 KB Output is correct
10 Correct 13 ms 5240 KB Output is correct
11 Correct 12 ms 5240 KB Output is correct
12 Correct 12 ms 5304 KB Output is correct
13 Correct 11 ms 5240 KB Output is correct
14 Correct 12 ms 5240 KB Output is correct
15 Correct 11 ms 5240 KB Output is correct
16 Correct 12 ms 5240 KB Output is correct
17 Correct 11 ms 5240 KB Output is correct
18 Correct 12 ms 5240 KB Output is correct
19 Correct 13 ms 5240 KB Output is correct
20 Correct 15 ms 5240 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5240 KB Output is correct
2 Correct 9 ms 5240 KB Output is correct
3 Correct 5 ms 5240 KB Output is correct
4 Correct 6 ms 5244 KB Output is correct
5 Correct 8 ms 5240 KB Output is correct
6 Correct 7 ms 5240 KB Output is correct
7 Correct 6 ms 5240 KB Output is correct
8 Correct 8 ms 5240 KB Output is correct
9 Correct 8 ms 5240 KB Output is correct
10 Correct 13 ms 5240 KB Output is correct
11 Correct 12 ms 5240 KB Output is correct
12 Correct 12 ms 5304 KB Output is correct
13 Correct 11 ms 5240 KB Output is correct
14 Correct 12 ms 5240 KB Output is correct
15 Correct 11 ms 5240 KB Output is correct
16 Correct 12 ms 5240 KB Output is correct
17 Correct 11 ms 5240 KB Output is correct
18 Correct 12 ms 5240 KB Output is correct
19 Correct 13 ms 5240 KB Output is correct
20 Correct 15 ms 5240 KB Output is correct
21 Correct 34 ms 5240 KB Output is correct
22 Correct 40 ms 5240 KB Output is correct
23 Correct 22 ms 5240 KB Output is correct
24 Correct 62 ms 5368 KB Output is correct
25 Correct 106 ms 5336 KB Output is correct
26 Correct 117 ms 5340 KB Output is correct
27 Correct 113 ms 5392 KB Output is correct
28 Correct 111 ms 5408 KB Output is correct
29 Correct 131 ms 5392 KB Output is correct
30 Correct 75 ms 5340 KB Output is correct
31 Correct 104 ms 5316 KB Output is correct
32 Correct 70 ms 5240 KB Output is correct
33 Correct 113 ms 5460 KB Output is correct
34 Correct 113 ms 5368 KB Output is correct
35 Correct 124 ms 5400 KB Output is correct
36 Correct 69 ms 5336 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5240 KB Output is correct
2 Correct 9 ms 5240 KB Output is correct
3 Correct 5 ms 5240 KB Output is correct
4 Correct 6 ms 5244 KB Output is correct
5 Correct 8 ms 5240 KB Output is correct
6 Correct 7 ms 5240 KB Output is correct
7 Correct 6 ms 5240 KB Output is correct
8 Correct 8 ms 5240 KB Output is correct
9 Correct 8 ms 5240 KB Output is correct
10 Correct 13 ms 5240 KB Output is correct
11 Correct 12 ms 5240 KB Output is correct
12 Correct 12 ms 5304 KB Output is correct
13 Correct 11 ms 5240 KB Output is correct
14 Correct 12 ms 5240 KB Output is correct
15 Correct 11 ms 5240 KB Output is correct
16 Correct 12 ms 5240 KB Output is correct
17 Correct 11 ms 5240 KB Output is correct
18 Correct 12 ms 5240 KB Output is correct
19 Correct 13 ms 5240 KB Output is correct
20 Correct 15 ms 5240 KB Output is correct
21 Correct 34 ms 5240 KB Output is correct
22 Correct 40 ms 5240 KB Output is correct
23 Correct 22 ms 5240 KB Output is correct
24 Correct 62 ms 5368 KB Output is correct
25 Correct 106 ms 5336 KB Output is correct
26 Correct 117 ms 5340 KB Output is correct
27 Correct 113 ms 5392 KB Output is correct
28 Correct 111 ms 5408 KB Output is correct
29 Correct 131 ms 5392 KB Output is correct
30 Correct 75 ms 5340 KB Output is correct
31 Correct 104 ms 5316 KB Output is correct
32 Correct 70 ms 5240 KB Output is correct
33 Correct 113 ms 5460 KB Output is correct
34 Correct 113 ms 5368 KB Output is correct
35 Correct 124 ms 5400 KB Output is correct
36 Correct 69 ms 5336 KB Output is correct
37 Incorrect 736 ms 5448 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5240 KB Output is correct
2 Correct 9 ms 5240 KB Output is correct
3 Correct 5 ms 5240 KB Output is correct
4 Correct 6 ms 5244 KB Output is correct
5 Correct 8 ms 5240 KB Output is correct
6 Correct 7 ms 5240 KB Output is correct
7 Correct 6 ms 5240 KB Output is correct
8 Correct 8 ms 5240 KB Output is correct
9 Correct 8 ms 5240 KB Output is correct
10 Correct 13 ms 5240 KB Output is correct
11 Correct 12 ms 5240 KB Output is correct
12 Correct 12 ms 5304 KB Output is correct
13 Correct 11 ms 5240 KB Output is correct
14 Correct 12 ms 5240 KB Output is correct
15 Correct 11 ms 5240 KB Output is correct
16 Correct 12 ms 5240 KB Output is correct
17 Correct 11 ms 5240 KB Output is correct
18 Correct 12 ms 5240 KB Output is correct
19 Correct 13 ms 5240 KB Output is correct
20 Correct 15 ms 5240 KB Output is correct
21 Correct 34 ms 5240 KB Output is correct
22 Correct 40 ms 5240 KB Output is correct
23 Correct 22 ms 5240 KB Output is correct
24 Correct 62 ms 5368 KB Output is correct
25 Correct 106 ms 5336 KB Output is correct
26 Correct 117 ms 5340 KB Output is correct
27 Correct 113 ms 5392 KB Output is correct
28 Correct 111 ms 5408 KB Output is correct
29 Correct 131 ms 5392 KB Output is correct
30 Correct 75 ms 5340 KB Output is correct
31 Correct 104 ms 5316 KB Output is correct
32 Correct 70 ms 5240 KB Output is correct
33 Correct 113 ms 5460 KB Output is correct
34 Correct 113 ms 5368 KB Output is correct
35 Correct 124 ms 5400 KB Output is correct
36 Correct 69 ms 5336 KB Output is correct
37 Incorrect 736 ms 5448 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5240 KB Output is correct
2 Correct 9 ms 5240 KB Output is correct
3 Correct 5 ms 5240 KB Output is correct
4 Correct 6 ms 5244 KB Output is correct
5 Correct 8 ms 5240 KB Output is correct
6 Correct 7 ms 5240 KB Output is correct
7 Correct 6 ms 5240 KB Output is correct
8 Correct 8 ms 5240 KB Output is correct
9 Correct 8 ms 5240 KB Output is correct
10 Correct 13 ms 5240 KB Output is correct
11 Correct 12 ms 5240 KB Output is correct
12 Correct 12 ms 5304 KB Output is correct
13 Correct 11 ms 5240 KB Output is correct
14 Correct 12 ms 5240 KB Output is correct
15 Correct 11 ms 5240 KB Output is correct
16 Correct 12 ms 5240 KB Output is correct
17 Correct 11 ms 5240 KB Output is correct
18 Correct 12 ms 5240 KB Output is correct
19 Correct 13 ms 5240 KB Output is correct
20 Correct 15 ms 5240 KB Output is correct
21 Correct 34 ms 5240 KB Output is correct
22 Correct 40 ms 5240 KB Output is correct
23 Correct 22 ms 5240 KB Output is correct
24 Correct 62 ms 5368 KB Output is correct
25 Correct 106 ms 5336 KB Output is correct
26 Correct 117 ms 5340 KB Output is correct
27 Correct 113 ms 5392 KB Output is correct
28 Correct 111 ms 5408 KB Output is correct
29 Correct 131 ms 5392 KB Output is correct
30 Correct 75 ms 5340 KB Output is correct
31 Correct 104 ms 5316 KB Output is correct
32 Correct 70 ms 5240 KB Output is correct
33 Correct 113 ms 5460 KB Output is correct
34 Correct 113 ms 5368 KB Output is correct
35 Correct 124 ms 5400 KB Output is correct
36 Correct 69 ms 5336 KB Output is correct
37 Incorrect 736 ms 5448 KB Output isn't correct
38 Halted 0 ms 0 KB -