Submission #490573

#	Time	Username	Problem	Language	Result	Execution time	Memory
490573		DeadlyCritic	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	910 ms	844 KiB

sculpture

#include <bits/stdc++.h>
// #pragma GCC optimize ("O2,unroll-loops")
// #pragma GCC optimize("no-stack-protector,fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define IOS ios::sync_with_stdio(0), cin.tie(), cout.tie();

#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define uni(v) sort(all(v)), v.erase(unique(all(v)), v.end())

// #define c0 (v << 1)
// #define c1 (c0 | 1)
// #define md ((l+r)>>1)

using namespace std;

typedef long long ll;

const int maxN = 2e3+7;
const int maxBt = 42;

ll pef[maxN];
int y[maxN];
bitset<maxN> dp[maxN];

inline ll range(int l, int r){
    return pef[r+1]-pef[l];
}

signed main(){IOS

    int n;
    int a, b;
    cin >> n >> a >> b;
    for(int i = 0; i < n; i++){
        cin >> y[i];
    }

    ll ans = 0;
    ll bads = 0;

    pef[0] = 0;
    for(int i = 0; i < n; i++)pef[i+1] = pef[i]+y[i];

    ll maxAns = 1ll << (maxBt+1);
    ll w = 1ll << maxBt;

    for(int bit = maxBt; bit >= 0; bit--){
        bads += w;

        for(int i = 0; i <= n; i++)for(int j = 0; j <= n; j++)dp[i][j] = 0;
        for(int i = a; i <= b; i++)dp[0][i] = 1;

        for(int i = 0; i < n; i++){
            for(int j = 0; j <= i; j++){
                if(range(j, i) >= maxAns)break;
                if((range(j, i) & bads) == 0){
                    dp[i+1] |= dp[j] >> 1;
                }
            }
        }

        if(dp[n][0] == 0){
            bads ^= w;
            ans ^= w;
        }
        w >>= 1;
    }

    cout << ans << '\n';
}

/*
6 1 3
8 1 2 1 5 4
*/

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