oj.uz

Submission #229849

# Submission time Handle Problem Language Result Execution time Memory
229849 2020-05-06T20:56:29 Z pedroslrey Bootfall (IZhO17_bootfall) C++14
0 / 100
 5 ms 512 KB 
//Bootfall subtask 1

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

using pii = pair<int, int>;
using lli = long long int;

#define debug(args...) fprintf(stderr, args)
#define pb push_back
#define fi first
#define se second
#define all(xs) xs.begin(), xs.end()

const int INF = 1e9;

int xs[110];
int dp[110][10010];

int marc[10010];

void make_dp(int n, int s, int ignore) {
	dp[0][0] = 1;
	for (int i = 1; i <= n; ++i) {
		for (int x = 0; x <= s; ++x) {
			if (i == ignore) {
				dp[i][x] = dp[i-1][x];
				continue;
			}
			int k = 0;
			if (x - xs[i] >= 0) k = dp[i-1][x - xs[i]];
			dp[i][x] = dp[i-1][x] | k;
		}
	}
}

void solve(int n) {
	int s = 0;
	for (int i = 1; i <= n; ++i)
		s += xs[i];

	make_dp(n, s, 0);
	if (!dp[n][s/2] || s%2 == 1) {
		printf("0\n");
		return;
	}

	for (int i = 1; i <= n; ++i) {
		make_dp(n, s, i);
		for (int k = 1; k <= s; ++k) {
			if ((s - xs[i] + k)%2 == 1) marc[k] = 0;
			if (dp[n][((s - xs[i] + k)/2 - k)]) ++marc[k];
		}
	}

	int maxi = 0;
	for (int k = 1; k <= s; ++k) 
		maxi = max(maxi, marc[k]);

	vector<int> ans;
	for (int k = 1; k <= s; ++k) 
		if (marc[k] == maxi && maxi != 0) ans.pb(k);

	printf("%d\n", (int) ans.size());
	for (int a: ans) 
		printf("%d ", a);
	printf("\n");
}

int main() {
	int n;
	scanf("%d", &n);

	for (int i = 1; i <= n; ++i)
		scanf("%d", &xs[i]);

	solve(n);
}

Compilation message

bootfall.cpp:4:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
bootfall.cpp:5:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
bootfall.cpp: In function 'int main()':
bootfall.cpp:77:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
bootfall.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &xs[i]);
   ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Incorrect 4 ms 384 KB Output isn't correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Incorrect 4 ms 384 KB Output isn't correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Incorrect 4 ms 384 KB Output isn't correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Incorrect 4 ms 384 KB Output isn't correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Incorrect 4 ms 384 KB Output isn't correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Incorrect 4 ms 384 KB Output isn't correct