Submission #1028560

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028560		vjudge1	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	90 ms	4440 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll N = 2005, LG = 42;
ll n, x, y;
ll a[N], mn[N];
bool dp[N][N];

int main(){
    cin >> n >> x >> y;
    for (ll i = 1; i <= n; i ++)
        cin >> a[i], a[i] += a[i - 1];

    ll ans = 0;
    for (ll bit = LG - 1; bit >= 0; bit --){
        memset(mn, 31, sizeof mn);
        ll mask = ans;
        mask |= ((1ll << bit) - 1);

        for (ll i = 1; i <= n; i ++){
            if (((a[i] & mask) == a[i]))
                mn[i] = 1;
            for (ll j = 1; j < i; j ++)
                if (((a[i] - a[j]) & mask) == (a[i] - a[j]))
                    mn[i] = min(mn[i], mn[j] + 1);
        }

        if (x == 1){
            if (mn[n] > y)
                ans += (1ll << bit);
            continue;
        }

        memset(dp, 0, sizeof dp);
        for (ll i = 1; i <= n; i ++){
            dp[i][1] = ((a[i] & mask) == a[i]);
            for (ll splits = 2; splits <= i; splits ++){
                for (ll j = splits - 1; j < i; j ++){
                    dp[i][splits] |= (dp[j][splits - 1] && (((a[i] - a[j]) & mask) == (a[i] - a[j])));
                }
            }
        }

        bool good = 0;
        for (ll i = x; i <= y; i ++)
            good |= dp[n][i];

        if (!good) ans += (1ll << bit);
    }

    cout << ans << endl;
}

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