Submission #464872

#	Time	Username	Problem	Language	Result	Execution time	Memory
464872		TeaTime	Bootfall (IZhO17_bootfall)	C++17	0 / 100	15 ms	1520 KiB

bootfall

//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>
#include <bitset>

using namespace std;

#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

typedef long long ll;
typedef long double ld;

#define int ll
const ll INF = 1e9, SZ = 510 * 510, SZ2 = 510;

ll n;
vector<ll> vec;
bitset<SZ> bts;
bitset<SZ> pref[SZ2], suf[SZ2], un[SZ2];

signed main() {
    fastInp;

    cin >> n;
    vec.resize(n);

    for (auto& c : vec) cin >> c;

    bts[0] = 1;
    ll sm = 0;

    pref[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        pref[i] = (pref[i - 1] | (pref[i - 1] << vec[i - 1]));
    }

    suf[n][0] = 1;
    for (int i = n - 1; i >= 0; i--) {
        suf[i] = (suf[i + 1] | (suf[i + 1] << vec[i]));
    }

    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j < SZ2; j++) {
            if (pref[i][j]) un[i] |= (suf[i + 1] << j);
        }
    }

    for (auto c : vec) {
        sm += c;
        bts |= (bts << c);
    }

    if (sm % 2) {
        cout << "0";
        return 0;
    }

    if (bts[sm / 2] != 1) {
        cout << "0";
        return 0;
    }

    vector<ll> ans;

    for (int i = 0; i < SZ; i++) {
        bool f = 1;
        for (int j = 0; j < n; j++) {
            ll cursm = sm - vec[j] + i;
            if (cursm % 2) {
                f = 0;
                break;
            }

            cursm /= 2;
            if (i > cursm) {
                f = 0;
                break;
            }

            if (un[j][cursm - i]) continue;

            f = 0;
            break;
        }

        if (f) ans.push_back(i);
    }

    cout << ans.size() << "\n";
    for (auto c : ans) cout << c << " ";
   
    return 0;
}

/*
3 4
RGWR
GRGG
RGWW

4 4
RGWR
GRRG
WGGW
WWWR

5 5
RGRGW
GRRGW
WGGWR
RWRGW
RGWGW
*/

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