oj.uz

Submission #93012

# Submission time Handle Problem Language Result Execution time Memory
93012 2019-01-06T09:55:13 Z emil_physmath Bootfall (IZhO17_bootfall) C++17
28 / 100
 1000 ms 38252 KB 
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int MAXN=300;

int a[MAXN];
vector<int> sums[MAXN];

vector<int> AllPossSums(int arr[], int n);
int main()
{
	int n, sum=0;
	cin>>n;
	for (int i=0; i<n; i++)
		cin>>a[i];
	for (int i=0; i<n; i++)
	{
		sum+=a[i];
		swap(a[i], a[n-1]);
		sums[i]=AllPossSums(a, n-1);
		swap(a[i], a[n-1]);
	}
	vector<int> temp=AllPossSums(a, n);
	if (sum%2 || *lower_bound(temp.begin(), temp.end(), sum/2)!=sum/2)
	{
		cout<<"0\n";
		return 0;
	}
	vector<int> ans;
	for (int x=1; x<=sum; x++)
	{
		bool isAns=true;
		for (int i=0; i<n; i++)
		{
			if ((sum-a[i]+x)%2) {
				isAns=false;
				break;
			}
			auto it=lower_bound(sums[i].begin(), sums[i].end(), (sum-a[i]+x)/2-x);
			if (it==sums[i].end() || *it!=(sum-a[i]+x)/2-x) {
				isAns=false;
				break;
			}
		}
		if (isAns)
			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][100000];
vector<int> AllPossSums(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]==true)
			res.push_back(j);
	return res;
}

Compilation message

bootfall.cpp: In function 'int main()':
bootfall.cpp:52: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 51 ms 29816 KB Output is correct
2 Correct 68 ms 29788 KB Output is correct
3 Correct 47 ms 29640 KB Output is correct
4 Correct 33 ms 29688 KB Output is correct
5 Correct 72 ms 29788 KB Output is correct
6 Correct 42 ms 29688 KB Output is correct
7 Correct 40 ms 29660 KB Output is correct
8 Correct 49 ms 29688 KB Output is correct
9 Correct 59 ms 29688 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 29816 KB Output is correct
2 Correct 68 ms 29788 KB Output is correct
3 Correct 47 ms 29640 KB Output is correct
4 Correct 33 ms 29688 KB Output is correct
5 Correct 72 ms 29788 KB Output is correct
6 Correct 42 ms 29688 KB Output is correct
7 Correct 40 ms 29660 KB Output is correct
8 Correct 49 ms 29688 KB Output is correct
9 Correct 59 ms 29688 KB Output is correct
10 Correct 95 ms 29688 KB Output is correct
11 Correct 95 ms 29688 KB Output is correct
12 Correct 85 ms 29688 KB Output is correct
13 Correct 88 ms 29660 KB Output is correct
14 Correct 92 ms 29816 KB Output is correct
15 Correct 82 ms 29688 KB Output is correct
16 Correct 251 ms 29816 KB Output is correct
17 Correct 162 ms 29688 KB Output is correct
18 Correct 209 ms 29688 KB Output is correct
19 Correct 221 ms 29720 KB Output is correct
20 Correct 242 ms 29788 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 29816 KB Output is correct
2 Correct 68 ms 29788 KB Output is correct
3 Correct 47 ms 29640 KB Output is correct
4 Correct 33 ms 29688 KB Output is correct
5 Correct 72 ms 29788 KB Output is correct
6 Correct 42 ms 29688 KB Output is correct
7 Correct 40 ms 29660 KB Output is correct
8 Correct 49 ms 29688 KB Output is correct
9 Correct 59 ms 29688 KB Output is correct
10 Correct 95 ms 29688 KB Output is correct
11 Correct 95 ms 29688 KB Output is correct
12 Correct 85 ms 29688 KB Output is correct
13 Correct 88 ms 29660 KB Output is correct
14 Correct 92 ms 29816 KB Output is correct
15 Correct 82 ms 29688 KB Output is correct
16 Correct 251 ms 29816 KB Output is correct
17 Correct 162 ms 29688 KB Output is correct
18 Correct 209 ms 29688 KB Output is correct
19 Correct 221 ms 29720 KB Output is correct
20 Correct 242 ms 29788 KB Output is correct
21 Correct 421 ms 30800 KB Output is correct
22 Correct 510 ms 31016 KB Output is correct
23 Correct 363 ms 30336 KB Output is correct
24 Correct 599 ms 32248 KB Output is correct
25 Correct 748 ms 32856 KB Output is correct
26 Correct 363 ms 32888 KB Output is correct
27 Correct 401 ms 31480 KB Output is correct
28 Correct 606 ms 31480 KB Output is correct
29 Correct 445 ms 32248 KB Output is correct
30 Correct 372 ms 32120 KB Output is correct
31 Correct 372 ms 32888 KB Output is correct
32 Correct 377 ms 32120 KB Output is correct
33 Correct 434 ms 29944 KB Output is correct
34 Correct 443 ms 29816 KB Output is correct
35 Correct 472 ms 31292 KB Output is correct
36 Correct 493 ms 32248 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 29816 KB Output is correct
2 Correct 68 ms 29788 KB Output is correct
3 Correct 47 ms 29640 KB Output is correct
4 Correct 33 ms 29688 KB Output is correct
5 Correct 72 ms 29788 KB Output is correct
6 Correct 42 ms 29688 KB Output is correct
7 Correct 40 ms 29660 KB Output is correct
8 Correct 49 ms 29688 KB Output is correct
9 Correct 59 ms 29688 KB Output is correct
10 Correct 95 ms 29688 KB Output is correct
11 Correct 95 ms 29688 KB Output is correct
12 Correct 85 ms 29688 KB Output is correct
13 Correct 88 ms 29660 KB Output is correct
14 Correct 92 ms 29816 KB Output is correct
15 Correct 82 ms 29688 KB Output is correct
16 Correct 251 ms 29816 KB Output is correct
17 Correct 162 ms 29688 KB Output is correct
18 Correct 209 ms 29688 KB Output is correct
19 Correct 221 ms 29720 KB Output is correct
20 Correct 242 ms 29788 KB Output is correct
21 Correct 421 ms 30800 KB Output is correct
22 Correct 510 ms 31016 KB Output is correct
23 Correct 363 ms 30336 KB Output is correct
24 Correct 599 ms 32248 KB Output is correct
25 Correct 748 ms 32856 KB Output is correct
26 Correct 363 ms 32888 KB Output is correct
27 Correct 401 ms 31480 KB Output is correct
28 Correct 606 ms 31480 KB Output is correct
29 Correct 445 ms 32248 KB Output is correct
30 Correct 372 ms 32120 KB Output is correct
31 Correct 372 ms 32888 KB Output is correct
32 Correct 377 ms 32120 KB Output is correct
33 Correct 434 ms 29944 KB Output is correct
34 Correct 443 ms 29816 KB Output is correct
35 Correct 472 ms 31292 KB Output is correct
36 Correct 493 ms 32248 KB Output is correct
37 Execution timed out 1081 ms 38252 KB Time limit exceeded
38 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 29816 KB Output is correct
2 Correct 68 ms 29788 KB Output is correct
3 Correct 47 ms 29640 KB Output is correct
4 Correct 33 ms 29688 KB Output is correct
5 Correct 72 ms 29788 KB Output is correct
6 Correct 42 ms 29688 KB Output is correct
7 Correct 40 ms 29660 KB Output is correct
8 Correct 49 ms 29688 KB Output is correct
9 Correct 59 ms 29688 KB Output is correct
10 Correct 95 ms 29688 KB Output is correct
11 Correct 95 ms 29688 KB Output is correct
12 Correct 85 ms 29688 KB Output is correct
13 Correct 88 ms 29660 KB Output is correct
14 Correct 92 ms 29816 KB Output is correct
15 Correct 82 ms 29688 KB Output is correct
16 Correct 251 ms 29816 KB Output is correct
17 Correct 162 ms 29688 KB Output is correct
18 Correct 209 ms 29688 KB Output is correct
19 Correct 221 ms 29720 KB Output is correct
20 Correct 242 ms 29788 KB Output is correct
21 Correct 421 ms 30800 KB Output is correct
22 Correct 510 ms 31016 KB Output is correct
23 Correct 363 ms 30336 KB Output is correct
24 Correct 599 ms 32248 KB Output is correct
25 Correct 748 ms 32856 KB Output is correct
26 Correct 363 ms 32888 KB Output is correct
27 Correct 401 ms 31480 KB Output is correct
28 Correct 606 ms 31480 KB Output is correct
29 Correct 445 ms 32248 KB Output is correct
30 Correct 372 ms 32120 KB Output is correct
31 Correct 372 ms 32888 KB Output is correct
32 Correct 377 ms 32120 KB Output is correct
33 Correct 434 ms 29944 KB Output is correct
34 Correct 443 ms 29816 KB Output is correct
35 Correct 472 ms 31292 KB Output is correct
36 Correct 493 ms 32248 KB Output is correct
37 Execution timed out 1081 ms 38252 KB Time limit exceeded
38 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 29816 KB Output is correct
2 Correct 68 ms 29788 KB Output is correct
3 Correct 47 ms 29640 KB Output is correct
4 Correct 33 ms 29688 KB Output is correct
5 Correct 72 ms 29788 KB Output is correct
6 Correct 42 ms 29688 KB Output is correct
7 Correct 40 ms 29660 KB Output is correct
8 Correct 49 ms 29688 KB Output is correct
9 Correct 59 ms 29688 KB Output is correct
10 Correct 95 ms 29688 KB Output is correct
11 Correct 95 ms 29688 KB Output is correct
12 Correct 85 ms 29688 KB Output is correct
13 Correct 88 ms 29660 KB Output is correct
14 Correct 92 ms 29816 KB Output is correct
15 Correct 82 ms 29688 KB Output is correct
16 Correct 251 ms 29816 KB Output is correct
17 Correct 162 ms 29688 KB Output is correct
18 Correct 209 ms 29688 KB Output is correct
19 Correct 221 ms 29720 KB Output is correct
20 Correct 242 ms 29788 KB Output is correct
21 Correct 421 ms 30800 KB Output is correct
22 Correct 510 ms 31016 KB Output is correct
23 Correct 363 ms 30336 KB Output is correct
24 Correct 599 ms 32248 KB Output is correct
25 Correct 748 ms 32856 KB Output is correct
26 Correct 363 ms 32888 KB Output is correct
27 Correct 401 ms 31480 KB Output is correct
28 Correct 606 ms 31480 KB Output is correct
29 Correct 445 ms 32248 KB Output is correct
30 Correct 372 ms 32120 KB Output is correct
31 Correct 372 ms 32888 KB Output is correct
32 Correct 377 ms 32120 KB Output is correct
33 Correct 434 ms 29944 KB Output is correct
34 Correct 443 ms 29816 KB Output is correct
35 Correct 472 ms 31292 KB Output is correct
36 Correct 493 ms 32248 KB Output is correct
37 Execution timed out 1081 ms 38252 KB Time limit exceeded
38 Halted 0 ms 0 KB -