Submission #62788

#	Time	Username	Problem	Language	Result	Execution time	Memory
62788		Tenuun	Bootfall (IZhO17_bootfall)	C++17	28 / 100	1074 ms	2324 KiB

bootfall

#include<bits/stdc++.h>
 
using namespace std;
 
int n, a[500], res[250001];

bool s[250001];

void check(){
	s[0]=true;
	vector<int> tmp;
	tmp.push_back(0);
	int sz;
	for(int i=0; i<n; i++){
		sz=tmp.size();
		for(int j=0; j<sz; j++){
			if(!s[tmp[j]+a[i]]){
				s[tmp[j]+a[i]]=true;
				tmp.push_back(tmp[j]+a[i]);
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int tot=0;
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> a[i];
		tot+=a[i];
	}
	memset(res, 0, sizeof res);
	memset(s, 0, sizeof s);
	check();
	if(tot%2 || !s[tot/2]){
		return cout << 0, 0;
	}
	int tmp;
	for(int i=0; i<n; i++){
		tmp=a[i];
		a[i]=0;
		memset(s, 0, sizeof s);
		check();
		tot-=tmp;
		for(int j=1; j<=tot; j++){
			if((tot+j)%2) continue;
			if(s[(tot+j)/2]){
				res[j]++;
			}
		}
		bool ok=false;
		for(int j=1; j<=tot; j++){
			if(res[j]==i+1) ok=true;
		}
		if(!ok) break;
		tot+=tmp;
		a[i]=tmp;
	}
	vector<int>res;
	for(int i=1; i<=tot; i++){
		if(::res[i]==n){
			res.push_back(i);
		}
	}
	cout << res.size() << endl;
	for(int i=0; i<res.size(); i++) cout << res[i] << " ";
	return 0;
}

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:68:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<res.size(); i++) cout << res[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