Submission #682397

#	Time	Username	Problem	Language	Result	Execution time	Memory
682397		iskhakkutbilim	Bootfall (IZhO17_bootfall)	C++14	13 / 100	1081 ms	340 KiB

bootfall

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int N = 500;
const int S = 500 * 500;
main(){
	int n; cin >> n;
	vector<int> a(n);
	int sum = 0, even = 0, odd = 0;
	for(int i = 0;i < n; i++){
		cin >> a[i];
		odd+= (a[i]%2==1);
		even+= (a[i]%2==0);
		sum+= a[i];
	}
	if(even > 0 and odd > 0){
		cout << 0;
		return 0;
	}
	if(sum%2==1){
		cout << 0;
		return 0;
	}
	vector<int> can;
	for(int tima = 1; tima <= 1000; tima++){
		sum+= tima;
		int ok = 1;
		for(int i = 0;i < a.size(); i++){
			if((sum-a[i])%2==1){
				ok = 0;
				break;
			}
		}
		if(ok) can.push_back(tima);
		sum-= tima;
	}
	
	
	vector<int> answer;
	for(int tima : can){
		sum+= tima;
		a.push_back(tima);
		int ok = 1;
		for(int i = 0;i < a.size(); i++){
			vector<int> dp(sum+1, 0);
			dp[0] = 1;
			for(int j = 0; j < a.size(); j++){
				if(i == j) continue;
				for(int s = sum; s >= 0; s--){
					if(s >= a[j]){
						dp[s] = max(dp[s], dp[s-a[j]]);
					}
				}
			}
			if(dp[(sum - a[i]) / 2] == 0){
				ok = 0;
				break;
			}
		}
		if(ok){
			answer.push_back(tima);
		}
		sum-= tima;
		a.pop_back();
	}
	cout << answer.size() << '\n';
	for(int x : answer) cout << x << ' ';
	return 0;
}

Compilation message (stderr)

bootfall.cpp:10:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   10 | main(){
      | ^~~~
bootfall.cpp: In function 'int main()':
bootfall.cpp:32:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   for(int i = 0;i < a.size(); i++){
      |                 ~~^~~~~~~~~~
bootfall.cpp:48:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |   for(int i = 0;i < a.size(); i++){
      |                 ~~^~~~~~~~~~
bootfall.cpp:51:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |    for(int j = 0; j < a.size(); j++){
      |                   ~~^~~~~~~~~~

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