Submission #145165

#	Time	Username	Problem	Language	Result	Execution time	Memory
145165		MathStudent2002	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	203 ms	632 KiB

sculpture

//wait darn

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll MAXK = 60;
const ll MAXN = 2019;
const ll INFTY = 2059;

ll cur;
int N;
int A, B;
bool b[MAXK];
bool cando[MAXN][MAXN];
ll few[MAXN];
ll psum[MAXN];
ll beau[MAXN];

void input() {
    cin >> N;
    cin >> A >> B;

    for(int i = 1; i <= N; i++) {cin >> beau[i];}
}

void init() {
    for(int i = 0; i < MAXK; i++) {b[i] = true;}
    for(int i = 1; i <= N; i++) {psum[i] = psum[i-1] + beau[i];}
}

void mindp() {
    for(int i = 0; i <= N; i++) {few[i] = INFTY;}
    few[0] = 0;
    for(int i = 1; i <= N; i++) {
        for(int j = 0; j < i; j++) {
            if(((psum[i]-psum[j])|cur) == cur && few[i] > few[j]+1)
                few[i] = few[j]+1;
        }
    }
}

void alldp() {
    for(int i = 0; i <= N; i++) {
        for(int j = 0; j <= N; j++) {
            cando[i][j] = false;
        }
    }

    cando[0][0] = true;

    for(int i = 0; i <= N; i++) {
        for(int j = 0; j < i; j++) {
            if(((psum[i]-psum[j])|cur) == cur) {
                for(int l = 0; l <= i; l++)
                    if(cando[j][l]) {cando[i][l+1] = true;}
            }
        }
    }
}

void solve() {
    for(int k = 0; k < MAXK; k++) {
        b[k] = false;
        cur = 0;
        for(int i = 0; i < MAXK; i++) {
            cur *= 2;
            cur += (b[i]?1:0);
        }

        if(A == 1) {
            mindp();
            if(few[N] > B) b[k] = true;
        }
        else {
            alldp();
            b[k] = true;
            for(int i = A; i <= B; i++) {
                b[k] &= (!cando[N][i]);
            }
        }
    }

    cur = 0;
    for(int i = 0; i < MAXK; i++) {
        cur *= 2;
        cur += (b[i]?1:0);
    }

    cout << cur << endl;
}

int main() {
    input();
    init();
    solve();
}

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