Submission #145159

#TimeUsernameProblemLanguageResultExecution timeMemory
145159MathStudent2002Bali Sculptures (APIO15_sculpture)C++14
0 / 100
2 ms380 KiB
//wait darn

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll MAXK = 5;
const ll MAXN = 2019;
const ll INFTY = 2019;

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++) {
            int x = psum[i] - psum[j];
            if((x|cur) == cur)
                few[i] = min(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 <= N-1; 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];
    }

    cout << cur << endl;
}

int main() {
    input();
    init();
    solve();
}
#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...