Submission #1294228

#TimeUsernameProblemLanguageResultExecution timeMemory
1294228Jawad_Akbar_JJBootfall (IZhO17_bootfall)C++20
100 / 100
404 ms3408 KiB
#include <iostream>

using namespace std;
const int N = 505, M = N * N, mod = 1e9 + 7;
int Ws[M], fav[M], Ans, k, n, a[N], sm;

void Add(int &A, int b){
	A += b;
	if (A >= mod)
		A -= mod;
}

int main(){
	Ws[0] = 1;

	cin>>n;

	for (int i=1, vl;i<=n;i++){
		cin>>vl, a[vl]++;
		sm += vl;
		for (int j=M-1;j>=vl;j--)
			Add(Ws[j], Ws[j - vl]);
	}

	if (sm % 2 == 0 and Ws[sm / 2] != 0)
		k = 1;

	for (int i=1;i<N;i++){
		if (a[i] == 0)
			continue;
		for (int j=i;j<M;j++)
			Add(Ws[j], mod - Ws[j - i]);

		for (int j=1;j<M;j++){
			int nSum = sm - i + j, mid = nSum / 2;
			if (nSum % 2 == 0 and Ws[mid] + (mid  - j >= 0 ? Ws[mid - j] : 0) != 0)
				fav[j] += a[i];
		}

		for (int j=M-1;j>=i;j--)
			Add(Ws[j], Ws[j - i]);
	}

	for (int j=1;j<M;j++){
		if (k == 1 and fav[j] == n)
			Ans++;
	}

	cout<<Ans<<'\n';
	for (int j=1;j<M;j++){
		if (k == 1 and fav[j] == n)
			cout<<j<<' ';
	}
	cout<<'\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...