Submission #91411

#	Time	Username	Problem	Language	Result	Execution time	Memory
91411		davitmarg	Bootfall (IZhO17_bootfall)	C++17	28 / 100	1073 ms	30676 KiB

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;

int n,a[502],dp[502][502*502],num[502 * 502];
int sum;
vector<int> ans;
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		sum += a[i];
	}
	for (int k = 0; k <= n; k++)
	{
		dp[k][0] = 1;
		for (int i = 0; i < n; i++)
			if(i!=k)
				for (int j = sum-a[k]; j >= 0; j--)
					dp[k][j + a[i]] += dp[k][j];
		map<int, bool> used;
		if (k != n)
			for (int j = sum - a[k]-1; j >= 0; j--)
			{
				if (dp[k][j]==0 || used[abs(j - ((sum - a[k]) - j))]==1)
					continue;
				num[abs(j-((sum - a[k]) - j))]++;
				used[abs(j - ((sum - a[k]) - j))] = 1;
			}
	}

	if (sum % 2 || dp[n][sum / 2] == 0)
	{
		cout << 0 << endl;
		return 0;
	}
	
	for (int j = 0; j <= sum; j++)
		if (num[j] == n)
			ans.PB(j);

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

Compilation message (stderr)

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

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 15 / 15
• Subtask 4: 0 / 16
• Subtask 5: 0 / 21
• Subtask 6: 0 / 35