답안 #93012 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
93012	2019-01-06T09:55:13 Z	emil_physmath	Bootfall (IZhO17_bootfall)	C++17	28 / 100	1000 ms	38252 KB

bootfall

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #93012

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 7.0 / 7.0

Subtask #3 15.0 / 15.0

Subtask #4 0 / 16.0

Subtask #5 0 / 21.0

Subtask #6 0 / 35.0

Subtask #1
6.0 / 6.0

Subtask #2
7.0 / 7.0

Subtask #3
15.0 / 15.0

Subtask #4
0 / 16.0

Subtask #5
0 / 21.0

Subtask #6
0 / 35.0