Submission #715719

#	Time	Username	Problem	Language	Result	Execution time	Memory
715719		lukameladze	Bootfall (IZhO17_bootfall)	C++14	100 / 100	442 ms	5772 KiB

bootfall

# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
 #define int long long
#define pii pair <int, int>
#define pb push_back
const int N = 3e5 + 5;
int t,n,a[N],dp[N], ans[N], sum;
main() {
	std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	vector <int> res;
	cin>>n;
	for (int i = 1; i <= n; i++) {
		cin>>a[i]; sum += a[i];
	}
	sort(a + 1, a + n + 1);
	dp[0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = sum; j >= a[i]; j--) {
			dp[j] += dp[j - a[i]];
		}
	}
	if (!sum % 2 || !dp[sum / 2]) {
		cout<<0<<"\n"; exit(0);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = a[i]; j <= sum; j++) {
			dp[j] -= dp[j - a[i]];
		}
		sum -= a[i];
		for (int j = 0; j <= sum; j++) {
			if (dp[j] && sum - 2 * j >= 0) {
				ans[sum - 2 * j]++;
				if (ans[sum - 2 * j] == n) res.pb(sum - 2 * j);
			}
		}
		sum += a[i];
		for (int j = sum; j >= a[i]; j--) {
			dp[j] += dp[j - a[i]];
		}
	}
	cout<<res.size()<<"\n"; 
	sort(res.begin(),res.end());
	for (int x : res) {
		cout<<x<<" ";		
	}
	cout<<"\n";
}

Compilation message (stderr)

bootfall.cpp:10:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   10 | 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