제출 #1327551

#제출 시각아이디문제언어결과실행 시간메모리
1327551AzeTurk810Bali Sculptures (APIO15_sculpture)C++20
100 / 100
112 ms21584 KiB
/*
Telebe of Adicto && Mamedov yani AzeTurk810
I see humans but no humanity
*/
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

using ll = long long;
using namespace std;

#define ln '\n'
#define INFi 1e18
#define INFll 1e18

#ifdef ONPC
#include <algo.hpp>
#else
#define dbg(...)
#define dbg_out(...)
#endif
#define int ll

constexpr int K = 60; // 505

char solve() {
    int N, A, B;
    if (!(cin >> N >> A >> B))
        return 1;
    vector<int> Y(N + 1), pref(N + 1);
    for (int i = 1; i <= N; i++)
        cin >> Y[i];
    for (int i = 1; i <= N; i++) {
        pref[i] = pref[i - 1] + Y[i];
    }
    auto sum = [&](int r, int l) {
        assert(l <= r);
        assert(r <= pref.size());
        assert(l >= 1);
        return pref[r] - pref[l - 1];
    };
    ll ans = 0;
    ll forbidden = 0;
    ll tot = pref[N];
    int mxBit = 0;
    if (tot > 0) {
        mxBit = 63 - __builtin_clzll(tot);
    } else 
        mxBit = 0;
    for (int bit = mxBit; bit >= 0; --bit) {
        ll tar = forbidden | (1LL << bit);
        vector<vector<int>> g(N + 1);
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j <= N; j++) {
                ll s = sum(j, i + 1);
            dbg(i);
                if ((s & tar) == 0) {
                    g[i].push_back(j);
                }
            }
        }
    dbg("S");
        vector<char> cur(N + 1, 0), nxt(N + 1, 0);
        cur[0] = 1;
        char ok = false;
        for (int grp = 0; grp < B; grp++) {
            fill(nxt.begin(), nxt.end(), 0);
            bool any = false;
            for (int pos = 0; pos < N; pos++) {
                if (!cur[pos]) {
                    continue;
                }
                const auto &adj = g[pos];
                for (const int &j : adj) {
                    if (!nxt[j]) {
                        nxt[j] = 1;
                        any = true;
                    }
                }
            }
            if ( (grp + 1) >= A && (grp + 1) <= B && nxt[N]) {
                ok = true;
                break;
            }
            if (!any) 
                break;
            cur.swap(nxt);
        }
        if (ok) {
            forbidden = tar;
        } else {
            ans |= (1LL << bit);
        }
    }
    cout << ans << ln;
    return 0;
}

// Attack on titan<3

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    int t = 1e9;
    // cin >> t;
    for (int cases = 0; cases < t; cases++) {
        if (solve())
            break;
#ifdef ONPC
        cerr << "__________\n";
#endif
    }
}
// Just Imaginary
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⠀⠀⠀⢀⣴⣾⠀⠀⠀⡀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣦⣾⣿⣿⣿⣿⣿⡆⠁⠀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿⣿⣿⣿⣿⡿⠁⠀⡠⠂⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠠⠔⠚⣿⣿⣿⣿⣿⣦⡄⠀⠁⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⠠⠐⢂⠉⡀⣀⣤⣄⢻⣿⣿⡟⢈⡹⣿⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⡀⠄⠂⠈⠀⣶⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠘⣷⡀⠀⡀⠐⠂⠐⢄
⠀⠀⠀⠀⠀⠀⠀⣿⣿⠟⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣀⣾⣷⠯⠀⠤⠤⠄⠈
⠀⠀⠀⠀⠀⠀⣼⣿⡟⠀⠀⣹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣰⣿⠋⠀⠀⢠⣾⣿⣿⣿⣿⣿⣭⠟⢻⣿⣿⣿⣿⡿⠁⠀⠀⠀⠀
⠀⠀⠀⣀⣶⡟⠁⠀⢾⣶⣿⠟⠉⠈⢻⣿⣿⣿⣦⣜⠀⠛⠛⠿⠁⠀⠀⠀⠀⠀
⠚⠻⠿⠿⡿⠁⠀⢠⣿⣿⠁⠀⣠⠖⠋⠉⠻⣿⣿⣿⣶⡀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⣰⣿⡿⠃⠠⠊⠁⠀⠀⠀⠀⠈⢿⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⣴⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⣠⣾⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⢀⣴⠾⠟⠛⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
*/
#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...