제출 #14381

#제출 시각아이디문제언어결과실행 시간메모리
14381tncks0121Bali Sculptures (APIO15_sculpture)C++14
100 / 100
109 ms1756 KiB
#include <bits/stdc++.h>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <time.h>
#include <limits.h>

using namespace std;

typedef long long ll;
typedef double lf;

const int N_ = 2050;

int N, A, B;
ll S[N_];

ll ans;

bool tb1[105][105];

void solve1() {
    ans = 0;
    ll cur = 0;
    for(int b = 41; b >= 0; b--) {
        ll t = cur | (1ll << b);

        tb1[0][0] = true;
        for(int i = 1; i <= N; i++) for(int x = 1; x <= i; x++) {
            tb1[i][x] = false;
            for(int j = 0; j < i; j++) {
                ll s = S[i] - S[j];
                if((s & t) == 0) tb1[i][x] |= tb1[j][x - 1];
            }
        }

        bool good = false;
        for(int x = A; x <= B; x++) good |= tb1[N][x];

        if(good) {
            cur = t;
        }else {
            ans += 1ll << b;
        }
    }
}

int tb2[N_];

void solve2() {
    ans = 0;
    ll cur = 0;
    for(int b = 41; b >= 0; b--) {
        ll t = cur | (1ll << b);

        for(int i = 1; i <= N; i++) {
            tb2[i] = (int)1e6;
            for(int j = 0; j < i; j++) {
                ll s = S[i] - S[j];
                if((s & t) == 0) tb2[i] = min(tb2[i], tb2[j] + 1);
            }
        }

        //printf("%lld %lld %d\n", ans, 1ll<<b, tb2[N]);
        if(tb2[N] <= B) {
            cur = t;
        }else {
            ans += 1ll << b;
        }
    }
}

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    scanf("%d%d%d", &N, &A, &B);
    for(int i = 1; i <= N; i++) {
        int x; scanf("%d", &x);
        S[i] = S[i-1] + x;
    }

    if(N <= 100) {
        solve1();
    }else {
        solve2();
    }

    printf("%lld\n", ans);
    return 0;
}
#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...