답안 #35048 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
35048	2017-11-17T20:06:09 Z	model_code	Bootfall (IZhO17_bootfall)	C++11	13 / 100	1000 ms	2528 KB

bootfall

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>

#define ll long long
#define pb push_back
#define f first
#define s second
#define mp make_pair

using namespace std;

const int maxn = 5e2 + 11;

int n, a[maxn], s;
bool dp[2 * maxn * maxn];

int main() {
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		s += a[i];
	}

	if (s % 2 != 0) {
		cout << 0;
		return 0;
	}

	dp[0] = 1;
	s /= 2;

	for (int i = 0; i < n; ++i)
	for (int sum = s; sum >= 0; --sum)
		if (dp[sum] && sum + a[i] <= s) 
			dp[sum + a[i]] = 1;

	if (!dp[s]) {
		cout << 0;
		return 0;
	}

	vector < int > ans;

	for (int x = 0; x <= s + s; x++) {
	        bool ok = 1;

		for (int i = 0; i < n; ++i) {
       		        int curs = s + s - a[i] + x;
		        if (curs % 2 != 0) {
		        	ok = 0;
		        	break;
		        }
		        curs /= 2;
		        memset(dp, 0, sizeof(dp));
		        dp[0] = 1;

		        swap(a[i], x);
			
			for (int j = 0; j < n; ++j)
				for (int sum = curs; sum >= 0; --sum)
					if (dp[sum] && sum + a[j] <= curs) 
						dp[sum + a[j]] = 1;

			swap(a[i], x);
			
			if (!dp[curs]) {
				ok = 0;
				break;
			}
		}

		if (ok) 
			ans.pb(x);
	}

	cout << ans.size() << endl;
	for (int i = 0; i < ans.size(); ++i)
		cout << ans[i] << ' ';

	return 0;
}

Compilation message

bootfall.cpp: In function 'int main()':
bootfall.cpp:86:20: 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	0 ms	2528 KB	Output is correct
2	Correct	0 ms	2528 KB	Output is correct
3	Correct	0 ms	2528 KB	Output is correct
4	Correct	13 ms	2528 KB	Output is correct
5	Correct	123 ms	2528 KB	Output is correct
6	Correct	6 ms	2528 KB	Output is correct
7	Correct	6 ms	2528 KB	Output is correct
8	Correct	149 ms	2528 KB	Output is correct
9	Correct	9 ms	2528 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2528 KB	Output is correct
2	Correct	0 ms	2528 KB	Output is correct
3	Correct	0 ms	2528 KB	Output is correct
4	Correct	13 ms	2528 KB	Output is correct
5	Correct	123 ms	2528 KB	Output is correct
6	Correct	6 ms	2528 KB	Output is correct
7	Correct	6 ms	2528 KB	Output is correct
8	Correct	149 ms	2528 KB	Output is correct
9	Correct	9 ms	2528 KB	Output is correct
10	Correct	33 ms	2528 KB	Output is correct
11	Correct	133 ms	2528 KB	Output is correct
12	Correct	9 ms	2528 KB	Output is correct
13	Correct	9 ms	2528 KB	Output is correct
14	Correct	149 ms	2528 KB	Output is correct
15	Correct	106 ms	2528 KB	Output is correct
16	Correct	139 ms	2528 KB	Output is correct
17	Correct	49 ms	2528 KB	Output is correct
18	Correct	96 ms	2528 KB	Output is correct
19	Correct	83 ms	2528 KB	Output is correct
20	Correct	36 ms	2528 KB	Output is correct

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2528 KB	Output is correct
2	Correct	0 ms	2528 KB	Output is correct
3	Correct	0 ms	2528 KB	Output is correct
4	Correct	13 ms	2528 KB	Output is correct
5	Correct	123 ms	2528 KB	Output is correct
6	Correct	6 ms	2528 KB	Output is correct
7	Correct	6 ms	2528 KB	Output is correct
8	Correct	149 ms	2528 KB	Output is correct
9	Correct	9 ms	2528 KB	Output is correct
10	Correct	33 ms	2528 KB	Output is correct
11	Correct	133 ms	2528 KB	Output is correct
12	Correct	9 ms	2528 KB	Output is correct
13	Correct	9 ms	2528 KB	Output is correct
14	Correct	149 ms	2528 KB	Output is correct
15	Correct	106 ms	2528 KB	Output is correct
16	Correct	139 ms	2528 KB	Output is correct
17	Correct	49 ms	2528 KB	Output is correct
18	Correct	96 ms	2528 KB	Output is correct
19	Correct	83 ms	2528 KB	Output is correct
20	Correct	36 ms	2528 KB	Output is correct
21	Execution timed out	1000 ms	2528 KB	Execution timed out
22	Halted	0 ms	0 KB	-

Subtask #4
0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2528 KB	Output is correct
2	Correct	0 ms	2528 KB	Output is correct
3	Correct	0 ms	2528 KB	Output is correct
4	Correct	13 ms	2528 KB	Output is correct
5	Correct	123 ms	2528 KB	Output is correct
6	Correct	6 ms	2528 KB	Output is correct
7	Correct	6 ms	2528 KB	Output is correct
8	Correct	149 ms	2528 KB	Output is correct
9	Correct	9 ms	2528 KB	Output is correct
10	Correct	33 ms	2528 KB	Output is correct
11	Correct	133 ms	2528 KB	Output is correct
12	Correct	9 ms	2528 KB	Output is correct
13	Correct	9 ms	2528 KB	Output is correct
14	Correct	149 ms	2528 KB	Output is correct
15	Correct	106 ms	2528 KB	Output is correct
16	Correct	139 ms	2528 KB	Output is correct
17	Correct	49 ms	2528 KB	Output is correct
18	Correct	96 ms	2528 KB	Output is correct
19	Correct	83 ms	2528 KB	Output is correct
20	Correct	36 ms	2528 KB	Output is correct
21	Execution timed out	1000 ms	2528 KB	Execution timed out
22	Halted	0 ms	0 KB	-

Subtask #5
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2528 KB	Output is correct
2	Correct	0 ms	2528 KB	Output is correct
3	Correct	0 ms	2528 KB	Output is correct
4	Correct	13 ms	2528 KB	Output is correct
5	Correct	123 ms	2528 KB	Output is correct
6	Correct	6 ms	2528 KB	Output is correct
7	Correct	6 ms	2528 KB	Output is correct
8	Correct	149 ms	2528 KB	Output is correct
9	Correct	9 ms	2528 KB	Output is correct
10	Correct	33 ms	2528 KB	Output is correct
11	Correct	133 ms	2528 KB	Output is correct
12	Correct	9 ms	2528 KB	Output is correct
13	Correct	9 ms	2528 KB	Output is correct
14	Correct	149 ms	2528 KB	Output is correct
15	Correct	106 ms	2528 KB	Output is correct
16	Correct	139 ms	2528 KB	Output is correct
17	Correct	49 ms	2528 KB	Output is correct
18	Correct	96 ms	2528 KB	Output is correct
19	Correct	83 ms	2528 KB	Output is correct
20	Correct	36 ms	2528 KB	Output is correct
21	Execution timed out	1000 ms	2528 KB	Execution timed out
22	Halted	0 ms	0 KB	-

Subtask #6
0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2528 KB	Output is correct
2	Correct	0 ms	2528 KB	Output is correct
3	Correct	0 ms	2528 KB	Output is correct
4	Correct	13 ms	2528 KB	Output is correct
5	Correct	123 ms	2528 KB	Output is correct
6	Correct	6 ms	2528 KB	Output is correct
7	Correct	6 ms	2528 KB	Output is correct
8	Correct	149 ms	2528 KB	Output is correct
9	Correct	9 ms	2528 KB	Output is correct
10	Correct	33 ms	2528 KB	Output is correct
11	Correct	133 ms	2528 KB	Output is correct
12	Correct	9 ms	2528 KB	Output is correct
13	Correct	9 ms	2528 KB	Output is correct
14	Correct	149 ms	2528 KB	Output is correct
15	Correct	106 ms	2528 KB	Output is correct
16	Correct	139 ms	2528 KB	Output is correct
17	Correct	49 ms	2528 KB	Output is correct
18	Correct	96 ms	2528 KB	Output is correct
19	Correct	83 ms	2528 KB	Output is correct
20	Correct	36 ms	2528 KB	Output is correct
21	Execution timed out	1000 ms	2528 KB	Execution timed out
22	Halted	0 ms	0 KB	-

답안 #35048

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 7.0 / 7.0

Subtask #3 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
0 / 15.0

Subtask #4
0 / 16.0

Subtask #5
0 / 21.0

Subtask #6
0 / 35.0