Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include <set>
- #include <vector>
- #include <algorithm>
- using namespace std;
- const int N = 505;
- bool poss[505][250001];
- vector<int> answ, pos, pos2;
- int a[N], n, sumAll = 0;
- int dp[N * N];
- int main()
- {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- #else
- std::ios::sync_with_stdio(false);
- cin.tie(0);
- #endif
- cin >> n;
- for (int i = 0; i < n; i++) {
- cin >> a[i];
- sumAll += a[i];
- }
- sort(a, a + n);
- //reverse(a, a + n);
- for (int ign = 0; ign < n; ign++) {
- for (int i = 0; i <= 500 * 500; i++) {
- dp[i] = 1e9;
- }
- for (int i = 0; i < n; i++) {
- if (i != ign) {
- dp[a[i]] = min(i, dp[a[i]]);
- }
- }
- for (int sm = 0; sm <= 500 * 500; sm++) {
- if (dp[sm] == 1e9) {
- continue;
- }
- poss[ign][sm] = 1;
- int nextInd = dp[sm] + 1;
- if (nextInd == ign) {
- nextInd++;
- }
- dp[sm + a[nextInd]] = min(dp[sm + a[nextInd]], nextInd); // в конец
- dp[sm + a[nextInd] - a[dp[sm]]] = min(dp[sm + a[nextInd] - a[dp[sm]]], nextInd); // вместо
- }
- poss[ign][0] = 1;
- }
- if (sumAll % 2) { // вообще не разбить когда снимает
- cout << "0";
- return 0;
- }
- if (!poss[0][(sumAll) / 2 - a[0]]) { // тоже не разбить пока снимает
- cout << "0";
- return 0;
- }
- for (int str = 1; str <= sumAll; str++) {
- bool fl = 1;
- for (int i = 0; i < n; i++) {
- if (!poss[i][(sumAll + str - a[i]) / 2 - str] || (sumAll + str - a[i]) % 2) {
- fl = 0;
- }
- }
- if (fl) {
- answ.push_back(str);
- }
- }
- cout << answ.size() << "\n";
- for (auto h : answ) {
- cout << h << " ";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement