Submission #91477

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
91477	2018-12-27T16:30:27 Z	davitmarg	Bootfall (IZhO17_bootfall)	C++17	13 / 100	3 ms	608 KB

bootfall

/*
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;

LL n,a[5000006],cant[5000006];
LL sum,sm;
vector<LL> ans;
LL dp[5000006];

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

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

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

	for (LL i = 0; i < n; i++)
		add(a[i]);

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

Compilation message

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

Subtask #1

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	456 KB	Output is correct
3	Correct	2 ms	456 KB	Output is correct
4	Correct	2 ms	492 KB	Output is correct
5	Correct	2 ms	492 KB	Output is correct
6	Correct	2 ms	492 KB	Output is correct
7	Correct	2 ms	492 KB	Output is correct
8	Correct	2 ms	492 KB	Output is correct
9	Correct	2 ms	492 KB	Output is correct

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	456 KB	Output is correct
3	Correct	2 ms	456 KB	Output is correct
4	Correct	2 ms	492 KB	Output is correct
5	Correct	2 ms	492 KB	Output is correct
6	Correct	2 ms	492 KB	Output is correct
7	Correct	2 ms	492 KB	Output is correct
8	Correct	2 ms	492 KB	Output is correct
9	Correct	2 ms	492 KB	Output is correct
10	Correct	2 ms	492 KB	Output is correct
11	Correct	2 ms	532 KB	Output is correct
12	Correct	2 ms	536 KB	Output is correct
13	Correct	2 ms	536 KB	Output is correct
14	Correct	2 ms	536 KB	Output is correct
15	Correct	2 ms	536 KB	Output is correct
16	Correct	2 ms	536 KB	Output is correct
17	Correct	2 ms	536 KB	Output is correct
18	Correct	2 ms	592 KB	Output is correct
19	Correct	2 ms	608 KB	Output is correct
20	Correct	2 ms	608 KB	Output is correct

Subtask #3

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	456 KB	Output is correct
3	Correct	2 ms	456 KB	Output is correct
4	Correct	2 ms	492 KB	Output is correct
5	Correct	2 ms	492 KB	Output is correct
6	Correct	2 ms	492 KB	Output is correct
7	Correct	2 ms	492 KB	Output is correct
8	Correct	2 ms	492 KB	Output is correct
9	Correct	2 ms	492 KB	Output is correct
10	Correct	2 ms	492 KB	Output is correct
11	Correct	2 ms	532 KB	Output is correct
12	Correct	2 ms	536 KB	Output is correct
13	Correct	2 ms	536 KB	Output is correct
14	Correct	2 ms	536 KB	Output is correct
15	Correct	2 ms	536 KB	Output is correct
16	Correct	2 ms	536 KB	Output is correct
17	Correct	2 ms	536 KB	Output is correct
18	Correct	2 ms	592 KB	Output is correct
19	Correct	2 ms	608 KB	Output is correct
20	Correct	2 ms	608 KB	Output is correct
21	Correct	3 ms	608 KB	Output is correct
22	Incorrect	3 ms	608 KB	Output isn't correct
23	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	Correct	2 ms	456 KB	Output is correct
3	Correct	2 ms	456 KB	Output is correct
4	Correct	2 ms	492 KB	Output is correct
5	Correct	2 ms	492 KB	Output is correct
6	Correct	2 ms	492 KB	Output is correct
7	Correct	2 ms	492 KB	Output is correct
8	Correct	2 ms	492 KB	Output is correct
9	Correct	2 ms	492 KB	Output is correct
10	Correct	2 ms	492 KB	Output is correct
11	Correct	2 ms	532 KB	Output is correct
12	Correct	2 ms	536 KB	Output is correct
13	Correct	2 ms	536 KB	Output is correct
14	Correct	2 ms	536 KB	Output is correct
15	Correct	2 ms	536 KB	Output is correct
16	Correct	2 ms	536 KB	Output is correct
17	Correct	2 ms	536 KB	Output is correct
18	Correct	2 ms	592 KB	Output is correct
19	Correct	2 ms	608 KB	Output is correct
20	Correct	2 ms	608 KB	Output is correct
21	Correct	3 ms	608 KB	Output is correct
22	Incorrect	3 ms	608 KB	Output isn't correct
23	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	Correct	2 ms	456 KB	Output is correct
3	Correct	2 ms	456 KB	Output is correct
4	Correct	2 ms	492 KB	Output is correct
5	Correct	2 ms	492 KB	Output is correct
6	Correct	2 ms	492 KB	Output is correct
7	Correct	2 ms	492 KB	Output is correct
8	Correct	2 ms	492 KB	Output is correct
9	Correct	2 ms	492 KB	Output is correct
10	Correct	2 ms	492 KB	Output is correct
11	Correct	2 ms	532 KB	Output is correct
12	Correct	2 ms	536 KB	Output is correct
13	Correct	2 ms	536 KB	Output is correct
14	Correct	2 ms	536 KB	Output is correct
15	Correct	2 ms	536 KB	Output is correct
16	Correct	2 ms	536 KB	Output is correct
17	Correct	2 ms	536 KB	Output is correct
18	Correct	2 ms	592 KB	Output is correct
19	Correct	2 ms	608 KB	Output is correct
20	Correct	2 ms	608 KB	Output is correct
21	Correct	3 ms	608 KB	Output is correct
22	Incorrect	3 ms	608 KB	Output isn't correct
23	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	Correct	2 ms	456 KB	Output is correct
3	Correct	2 ms	456 KB	Output is correct
4	Correct	2 ms	492 KB	Output is correct
5	Correct	2 ms	492 KB	Output is correct
6	Correct	2 ms	492 KB	Output is correct
7	Correct	2 ms	492 KB	Output is correct
8	Correct	2 ms	492 KB	Output is correct
9	Correct	2 ms	492 KB	Output is correct
10	Correct	2 ms	492 KB	Output is correct
11	Correct	2 ms	532 KB	Output is correct
12	Correct	2 ms	536 KB	Output is correct
13	Correct	2 ms	536 KB	Output is correct
14	Correct	2 ms	536 KB	Output is correct
15	Correct	2 ms	536 KB	Output is correct
16	Correct	2 ms	536 KB	Output is correct
17	Correct	2 ms	536 KB	Output is correct
18	Correct	2 ms	592 KB	Output is correct
19	Correct	2 ms	608 KB	Output is correct
20	Correct	2 ms	608 KB	Output is correct
21	Correct	3 ms	608 KB	Output is correct
22	Incorrect	3 ms	608 KB	Output isn't correct
23	Halted	0 ms	0 KB	-