Submission #92745

#	Time	Username	Problem	Language	Result	Execution time	Memory
92745		janchomath	Bootfall (IZhO17_bootfall)	C++14	13 / 100	1082 ms	504 KiB

bootfall

#include<bits/stdc++.h>
#define ll int
#define f first
#define s second
#define pb push_back
using namespace std;
ll n,a[20005],dp[20005],sum,s,oo,x;
vector<ll>anss,v;
inline bool check(ll k){
	v.clear();
	
	s = 0;
	
	for(int i=1; i<=n; i++)if(i != k)v.pb(a[i]),s += a[i];
	if(s % 2 == 1)return false;
	
	for(int i=1; i<=s; i++)dp[i] = 0;
	dp[0] = 1;
	for(int i=0; i<v.size(); i++){
		for(int j=s; j>=0; j--){
			dp[j + v[i]] = max(dp[j],dp[j + v[i]]);
			if(dp[j + v[i]] && j + v[i] == s/2){
				return true;
			}
		}
	}
	
	return false;
	
}
int main(){
	std::ios::sync_with_stdio(false);
	
	cin >> n;
	
	for(int i=1; i<=n; i++){
		cin >> a[i];
		sum += a[i];
	}
	
	n++;
	
	for(x=1; x<=sum; x++){
		
		a[n] = x;
		
		oo = 0;
		for(int i=1; i<=n; i++){
			if(!check(i)){
				oo = 1;
				break;
			}
		}
		
		if(!oo){
			anss.pb(x);
		}
		
	}
	
	
	cout << anss.size() << endl;
	
	for(int i=0; i<anss.size(); i++)cout << anss[i] << " ";
	
	
	
	
	return 0;
}

Compilation message (stderr)

bootfall.cpp: In function 'bool check(int)':
bootfall.cpp:19:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size(); i++){
               ~^~~~~~~~~
bootfall.cpp: In function 'int main()':
bootfall.cpp:64:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<anss.size(); i++)cout << anss[i] << " ";
               ~^~~~~~~~~~~~

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