제출 #340060

#제출 시각아이디문제언어결과실행 시간메모리
340060SprdaloBootfall (IZhO17_bootfall)C++17
28 / 100
1081 ms504 KiB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pi> vp;
typedef vector<pl> vpl;

signed main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); 
    cout.tie(nullptr); 
    cerr.tie(nullptr);    

    int n;
    cin >> n;

    int a[n+1], suma = 0;
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
        suma += a[i];
    }

    vi s(suma+10, INT32_MAX);
    s[0] = 0;
    for (int i = 1; i <= n; ++i){
        for (int j = 0; j <= suma; ++j){
            if (s[j] < i){
                s[a[i]+j] = min(s[a[i]+j], i);
            }
        }
    }

    if (suma%2 || s[suma/2] == INT32_MAX)
        return cout << "0\n", 0;

    vi sol(suma+10, 1), moze(suma+10);
    for (int k = 1; k <= n; ++k){
        fill(s.begin(), s.end(), INT32_MAX);
        s[0] = 0;

        for (int i = 1; i <= n; ++i){
            if (i == k) continue;
            for (int j = 0; j <= suma; ++j){
                if (s[j] < i){
                    int y = suma - a[k] - 2 * j;
                    if (y > 0)
                    moze[y] = k;
                    s[a[i]+j] = min(s[a[i]+j], i);
                    int x = suma - a[k] - 2 * (a[i] + j);
                    if (x > 0)
                    moze[x]=k;
                }
            }
        }

        for (int i = 1; i < suma; ++i){
            if (moze[i]!=k || !sol[i])
                sol[i ] = 0;
        }
    }

    vi res;
    for (int i = 1; i < suma; ++i)
        if (sol[i])
            res.push_back(i);

    cout << (int)res.size() << '\n';
    for (auto& i : res)
        cout << i << ' ';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...