Submission #563220

#	Time	Username	Problem	Language	Result	Execution time	Memory
563220		Cyanmond	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	337 ms	348 KiB

sculpture

#include <bits/stdc++.h>

using namespace std;
using i64 = int64_t;

constexpr int inf = 1 << 25;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REP3(i, l, r) for (int i = (l); i < (r); ++i)
#define RVP(i, n) for (int i = (n - 1); i >= 0; --i)

#define ALL(x) (x).begin(), (x).end()

template <typename T> void chmax(T &a, const T b) {
    if (a < b) a = b;
}
template <typename T> void chmin(T &a, const T b) {
    if (a > b) a = b;
}

int main() {
    int N, A, B;
    cin >> N >> A >> B;
    ++B;
    vector<i64> Y(N);
    for (auto &e : Y) cin >> e;
    vector<i64> Yc(N + 1);
    REP(i, N) Yc[i + 1] = Yc[i] + Y[i];
    auto sum = [&Yc](int l, int r) { return Yc[r] - Yc[l]; };

    i64 ans = 0;
    RVP(b, 50) {
        vector<int> dpmin(N + 1, inf), dpmax(N + 1, -inf);
        dpmin[0] = dpmax[0] = 0;
        REP(i, N) {
            REP3(j, i + 1, N + 1) {
                const i64 s = sum(i, j);
                if (s & (1ll << b)) continue;
                const i64 t = s & (((1ll << 51) - 1) - ((1ll << b) - 1));
                if ((t & ans) != t) continue;
                chmin(dpmin[j], dpmin[i] + 1);
                chmax(dpmax[j], dpmax[i] + 1);
            }
        }
        const int k_l = dpmin[N], k_r = dpmax[N] + 1;
        if (max(A, k_l) >= min(B, k_r)) {
            ans |= 1ll << b;
        }
    }
    cout << ans << endl;
}

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 21 / 21
• Subtask 4: 25 / 25
• Subtask 5: 29 / 29