Submission #1237776

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237776		tin_le	Bali Sculptures (APIO15_sculpture)	C++20	100 / 100	66 ms	444 KiB

sculpture

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vvll = vector<vll>;
#define INF 1e9
const int B = 2005;
bitset<B> dp[B];
void solve() {
    int n, l, r; cin >> n >> l >> r;
    vll a(n); 
    for(auto& x : a) cin >> x;
    const int K = 41;
    ll cand = 0;
    for(int i = l; i <= r; i++) dp[n].set(i);
    auto f = [&](int b) -> bool {
        if(l == 1) {
            vll now(n + 1, INF);
            now[0] = 0;
            for(int i = 0; i < n; i++) {
                ll x = 0;
                for(int j = i; j >= 0; j--) {
                    x += a[j];
                    if((cand >> b) == (cand | x) >> b) {
                        now[i + 1] = min(now[i + 1], now[j] + 1);
                    }
                }
            }
            return now[n] <= r;
        }
        for(int i = n - 1; i >= 0; i--) {
            dp[i].reset();
            ll x = 0;
            bitset<B> now;
            for(int j = i; j < n; j++) {
                x += a[j];
                if((cand >> b) == (cand | x) >> b) {
                    dp[i] |= dp[j + 1] >> 1;
                }
            }
        }
        return dp[0][0];
    };
    for(int b = K - 1; b >= 0; b--) {
        if(f(b)) continue;
        cand ^= 1LL << b;
    }
    cout << cand << '\n';
}

signed main() {
    int t = 1;
    for(int i = 1; i <= t; i++) {   
        solve();
    }
    return 0;
}

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