oj.uz

Submission #92744

# Submission time Handle Problem Language Result Execution time Memory
92744 2019-01-04T12:25:59 Z janchomath Bootfall (IZhO17_bootfall) C++14
0 / 100
 2 ms 376 KB 
#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;
		if((x + sum)%2 == 1)continue;
		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

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:65:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<anss.size(); i++)cout << anss[i] << " ";
               ~^~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -