oj.uz

Submission #145158

# Submission time Handle Problem Language Result Execution time Memory
145158 2019-08-18T23:00:18 Z MathStudent2002 Bali Sculptures (APIO15_sculpture) C++14
21 / 100
 4 ms 508 KB 
//wait darn

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll MAXK = 41;
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();
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 2 ms 404 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 404 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Incorrect 2 ms 376 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Incorrect 3 ms 376 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 3 ms 504 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 3 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 376 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Correct 3 ms 376 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 3 ms 376 KB Output is correct
28 Correct 3 ms 376 KB Output is correct
29 Correct 3 ms 380 KB Output is correct
30 Correct 3 ms 380 KB Output is correct
31 Correct 3 ms 376 KB Output is correct
32 Correct 3 ms 376 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 1 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Incorrect 2 ms 376 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 4 ms 376 KB Output is correct
14 Correct 3 ms 376 KB Output is correct
15 Incorrect 2 ms 376 KB Output isn't correct
16 Halted 0 ms 0 KB -