제출 #1028560

#제출 시각아이디문제언어결과실행 시간메모리
1028560vjudge1Bali Sculptures (APIO15_sculpture)C++17
100 / 100
90 ms4440 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...