oj.uz

Submission #91430

# Submission time Handle Problem Language Result Execution time Memory
91430 2018-12-27T13:03:44 Z davitmarg Bootfall (IZhO17_bootfall) C++17
0 / 100
 2 ms 468 KB 
/*
DEATH-MATCH
Davit-Marg
*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <iterator>
#include <ctype.h>
#include <stdlib.h>  
#include <fstream>  
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
using namespace std;

int n,a[502],cant[502 * 502*10];
int sum;
vector<int> ans;
LL dp[502 * 502];

void add(LL k) {
	for (int i = sum; i >= k; i--) {
		dp[i] += dp[i - k];
	}
}

void rem(LL k) {
	for (int i = k; i <= sum; i++) {
		dp[i] -= dp[i - k];
	}
}

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

	for (int i = 0; i < n; i++)
		for (int j = sum; j >= 0; j--)
			dp[j + a[i]]+=dp[j];

	if (sum % 2==1 || dp[sum / 2] == 0)
	{
		cout << 0 << endl;
		return 0;
	}

	for (int i = 0; i < n; i++)
	{
		rem(a[i]);
		sum -= a[i];
		for (int j = 0; j <= sum+1; j++)
			if ((sum+j) % 2==1 || dp[(sum+j) / 2] == 0)
				cant[j] = 1;
		add(a[i]);
		sum += a[i];
	}
	for (int j = 0; j <= sum; j++)
		if (!cant[j])
			ans.PB(j);
	
	cout << ans.size() << endl;
	for (int i = 0; i < ans.size(); i++)
		cout << ans[i] << " ";
	cout << endl;
	return 0;
}

Compilation message

bootfall.cpp: In function 'int main()':
bootfall.cpp:79:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ans.size(); i++)
                  ~~^~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 468 KB Output isn't correct
3 Halted 0 ms 0 KB -