oj.uz

Submission #35048

# Submission time Handle Problem Language Result Execution time Memory
35048 2017-11-17T20:06:09 Z model_code Bootfall (IZhO17_bootfall) C++11
13 / 100
 1000 ms 2528 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -