Submission #1028557

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028557		vjudge1	Bali Sculptures (APIO15_sculpture)	C++17	71 / 100	1100 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];
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(dp, 0, sizeof dp);
        ll mask = ans;
        mask |= ((1ll << bit) - 1);

        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: 0 / 29