Submission #340060

#	Time	Username	Problem	Language	Result	Execution time	Memory
340060		Sprdalo	Bootfall (IZhO17_bootfall)	C++17	28 / 100	1081 ms	504 KiB

bootfall

#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 << ' ';
}

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