Submission #572090

#	Time	Username	Problem	Language	Result	Execution time	Memory
572090		ddy888	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	496 ms	856 KiB

sculpture

#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define fi first
#define si second
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;  
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 2010;
int n, a, b;
int arr[MAXN];
ll p[MAXN];

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 
    cin >> n >> a >> b;
    for (int i = 1; i <= n; ++i) cin >> arr[i], p[i] = p[i - 1] + arr[i];
    auto sum = [&](int l, int r) {
        return p[r] - p[l - 1];
    };
    auto possible = [&](ll x, ll msk) {
        return ((x | msk) == msk);
    };
    ll mask = (1ll << 41) - 1;
    for (int bit = 40; bit >= 0; --bit) {
        ll new_mask = mask ^ (1ll << bit);
        bitset<2010> f[n + 1];
        f[0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < i; ++j) {
                ll seg = sum(j + 1, i);
                if (possible(seg, new_mask)) {
                    f[i] |= (f[j] << 1ll);
                }
            }
        }
        bool flag = false;
        for (int j = a; j <= b; ++j) flag |= f[n][j];
        if (flag) mask = new_mask;
    }
    cout << mask;
    return 0;
}

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