Submission #14381

#	Time	Username	Problem	Language	Result	Execution time	Memory
14381		tncks0121	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	109 ms	1756 KiB

sculpture

#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;
}

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