Submission #346815

#	Time	Username	Problem	Language	Result	Execution time	Memory
346815		SeDunion	Bootfall (IZhO17_bootfall)	C++17	100 / 100	485 ms	3052 KiB

bootfall

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 505;
const int MX = 500 * 500 + 5;

const int mod = 1e9 + 7;
int a[N], d[MX], cnt[MX], Sum;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	d[0] = 1;
	for (int i = 1 ; i <= n ; ++ i) {
		cin >> a[i];
		Sum += a[i];
		for (int j = MX - 1 ; j >= a[i] ; -- j) {
			d[j] += d[j - a[i]];
			d[j] -= d[j] >= mod ? mod : 0;
		}
	}
	if (Sum & 1 || !d[Sum / 2]) return cout << "0", 0;
	for (int i = 1 ; i <= n ; ++ i) {
		int Now = Sum - a[i];
		//cout << i << " " << Now << endl;
		for (int j = a[i] ; j < MX ; ++ j) {
			d[j] -= d[j - a[i]];
			d[j] += d[j] < 0 ? mod : 0;
		}
		for (int j = Now & 1 ; j < MX ; j += 2) {
			int Cur = Now + j;
			cnt[j] += j <= (Cur >> 1) && !!d[(Cur >> 1) - j];
		}
		for (int j = MX - 1 ; j >= a[i] ; -- j) {
			d[j] += d[j - a[i]];
			d[j] -= d[j] >= mod ? mod : 0;
		}
	}
	int Cnt = 0;
	for (int i = 0 ; i < MX ; ++ i) Cnt += cnt[i] == n;
	cout << Cnt << "\n";
	for (int i = 0 ; i < MX ; ++ i) if (cnt[i] == n) cout << i << " ";
}

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