Submission #380037

#	Time	Username	Problem	Language	Result	Execution time	Memory
380037		Kalashnikov	Bootfall (IZhO17_bootfall)	C++17	100 / 100	146 ms	3584 KiB

bootfall

#include <bits/stdc++.h>
 
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define all(a) a.begin() , a.end()
#define F first
#define S second
 
using namespace std;
using ll = long long;
 
const int N = 500+5 , inf = 2e9 + 7;
const ll INF = 1e18 ,   mod = 1e9+7 , P = 6547;
 
int a[N] , u[N] , ans[N*N];
int dp[N*N]; 
 
void solve() {
	int n;
	cin >> n;
	ll sum = 0;
	int cnt[2];
	cnt[0]=cnt[1]=0;
	for(int i = 1; i <= n; i ++) {
		cin >> a[i];
		sum += a[i];
		cnt[a[i]%2] = 1;
	}
	if(sum % 2 || cnt[0] == cnt[1]) {
		cout << "0";
		return;
	}
	dp[0] = 1;
	for(int i = 1; i <= n; i ++) {
		for(int j = sum; j >= 0; j --) {
			if(j + a[i] <= sum) {
				dp[j+a[i]] += dp[j];
			}
		}
	}
	if(!dp[sum/2]) {
		cout << "0";
		return;
	}

	int f = 0;
	for(int i = 1; i <= n; i ++) {
		if(u[a[i]]) continue;
		u[a[i]] = 1;
		f ++;
		
		for(int j = 0; j < sum; j ++) {
			if(j + a[i] <= sum) {
				dp[j+a[i]] -= dp[j];
			}
		}
		sum -= a[i];
//		cout << a[i] << ": \n";
		for(int i = 2 - cnt[1]; i <= sum; i += 2) {
			if(dp[(sum+i) / 2]) {
	//			cout << "    " << i << '\n';
				ans[i] ++;
			}
		}
		
		sum += a[i];
		for(int j = sum; j >= 0; j --) {
			if(j + a[i] <= sum) {
				dp[j+a[i]] += dp[j];
			}
		}
	}
	
	vector<int> v;
	for(int i = 1; i < N*N; i ++) {
		if(ans[i] == f) {
			v.push_back(i);
		}
	}
	
	cout << v.size() << '\n';
	for(auto to: v) {
		cout << to << ' ';
	}
	
}
/*
1 2 1 2   2
 
 
*/
main() {
    ios;
    int tt = 1;
    //cin >> tt;
    while(tt --) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

bootfall.cpp:92:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   92 | main() {
      |      ^

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