oj.uz

Submission #634646

# Submission time Handle Problem Language Result Execution time Memory
634646 2022-08-24T16:20:34 Z tvladm2009 Bali Sculptures (APIO15_sculpture) C++14
25 / 100
 649 ms 262144 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#define int long long

using namespace std;

const int MAX_N = 2 * 1e3;
const int INF = (1LL << 60);
const int MAX_L = 11;
int y[MAX_N + 1], range[MAX_N + 1][MAX_N + 1];
vector<int> dp[MAX_N + 1][MAX_N + 1];
int n, a, b;

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> a >> b;
    int mx = 0;
    for (int i = 1; i <= n; i++) {
        cin >> y[i];
        mx = max(mx, n);
        range[i][i] = y[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            range[i][j] = range[i][j - 1] + y[j];
        }
    }
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            dp[i][j].push_back(INF);
        }
    }
    dp[0][0].push_back(0);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= i; k++) {
                for (int l = 0; l < min(50LL, (int)dp[k - 1][j - 1].size()); l++) {
                    dp[i][j].push_back(dp[k - 1][j - 1][l] | range[k][i]);
                }
            }
            sort(dp[i][j].begin(), dp[i][j].end());
            auto last = unique(dp[i][j].begin(), dp[i][j].end());
            dp[i][j].erase(last, dp[i][j].end());
        }
    }
    int answer = INF;
    for (int i = a; i <= b; i++) {
        for (int it : dp[n][i]) {
            answer = min(answer, it);
        }
    }
    cout << answer;
    return 0;
}
/*
20 1 3
9 9 8 8 10 8 8 8 8 9 9 8 8 8 9 8 10 8 9 8


*/

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 94284 KB Output is correct
2 Correct 58 ms 94312 KB Output is correct
3 Correct 50 ms 94324 KB Output is correct
4 Correct 49 ms 94284 KB Output is correct
5 Correct 46 ms 94420 KB Output is correct
6 Correct 48 ms 94564 KB Output is correct
7 Correct 52 ms 94676 KB Output is correct
8 Correct 51 ms 94936 KB Output is correct
9 Correct 51 ms 95192 KB Output is correct
10 Correct 47 ms 94924 KB Output is correct
11 Correct 47 ms 94924 KB Output is correct
12 Correct 47 ms 94948 KB Output is correct
13 Correct 50 ms 94908 KB Output is correct
14 Correct 57 ms 94284 KB Output is correct
15 Correct 60 ms 94292 KB Output is correct
16 Correct 49 ms 94284 KB Output is correct
17 Correct 47 ms 94284 KB Output is correct
18 Correct 47 ms 94416 KB Output is correct
19 Correct 47 ms 94580 KB Output is correct
20 Correct 49 ms 94796 KB Output is correct
21 Correct 50 ms 95000 KB Output is correct
22 Correct 49 ms 95108 KB Output is correct
23 Correct 47 ms 94944 KB Output is correct
24 Correct 49 ms 94884 KB Output is correct
25 Correct 53 ms 94932 KB Output is correct
26 Correct 51 ms 95052 KB Output is correct
27 Correct 46 ms 94284 KB Output is correct
28 Correct 47 ms 94416 KB Output is correct
29 Correct 47 ms 94668 KB Output is correct
30 Correct 52 ms 95504 KB Output is correct
31 Correct 56 ms 95308 KB Output is correct
32 Correct 50 ms 95308 KB Output is correct
33 Correct 49 ms 95052 KB Output is correct
34 Correct 49 ms 94900 KB Output is correct
35 Correct 47 ms 94732 KB Output is correct
36 Correct 49 ms 94688 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 94400 KB Output is correct
2 Correct 50 ms 94288 KB Output is correct
3 Correct 59 ms 94240 KB Output is correct
4 Correct 51 ms 94244 KB Output is correct
5 Correct 48 ms 94412 KB Output is correct
6 Correct 47 ms 94536 KB Output is correct
7 Correct 47 ms 94736 KB Output is correct
8 Correct 48 ms 94924 KB Output is correct
9 Correct 48 ms 95180 KB Output is correct
10 Correct 48 ms 94928 KB Output is correct
11 Correct 55 ms 94956 KB Output is correct
12 Correct 55 ms 94924 KB Output is correct
13 Correct 50 ms 95036 KB Output is correct
14 Correct 48 ms 94328 KB Output is correct
15 Correct 47 ms 94376 KB Output is correct
16 Correct 46 ms 94316 KB Output is correct
17 Correct 45 ms 94256 KB Output is correct
18 Correct 46 ms 94388 KB Output is correct
19 Correct 48 ms 94548 KB Output is correct
20 Correct 56 ms 94796 KB Output is correct
21 Correct 50 ms 95184 KB Output is correct
22 Correct 50 ms 95200 KB Output is correct
23 Correct 48 ms 94968 KB Output is correct
24 Correct 47 ms 94916 KB Output is correct
25 Correct 46 ms 94992 KB Output is correct
26 Correct 48 ms 95052 KB Output is correct
27 Correct 52 ms 95132 KB Output is correct
28 Correct 54 ms 96116 KB Output is correct
29 Correct 74 ms 102664 KB Output is correct
30 Correct 81 ms 105760 KB Output is correct
31 Correct 134 ms 115484 KB Output is correct
32 Correct 111 ms 113456 KB Output is correct
33 Correct 107 ms 113492 KB Output is correct
34 Correct 110 ms 113568 KB Output is correct
35 Correct 117 ms 114520 KB Output is correct
36 Correct 111 ms 114564 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 94332 KB Output is correct
2 Correct 47 ms 94352 KB Output is correct
3 Correct 46 ms 94292 KB Output is correct
4 Correct 50 ms 94360 KB Output is correct
5 Correct 46 ms 94360 KB Output is correct
6 Correct 49 ms 94544 KB Output is correct
7 Correct 50 ms 94676 KB Output is correct
8 Correct 54 ms 94936 KB Output is correct
9 Correct 52 ms 95112 KB Output is correct
10 Correct 56 ms 94896 KB Output is correct
11 Correct 48 ms 94992 KB Output is correct
12 Correct 47 ms 94888 KB Output is correct
13 Correct 50 ms 95020 KB Output is correct
14 Correct 51 ms 95156 KB Output is correct
15 Correct 63 ms 96008 KB Output is correct
16 Correct 76 ms 102728 KB Output is correct
17 Correct 82 ms 105832 KB Output is correct
18 Correct 116 ms 115452 KB Output is correct
19 Correct 109 ms 113484 KB Output is correct
20 Correct 124 ms 113404 KB Output is correct
21 Correct 117 ms 113624 KB Output is correct
22 Correct 112 ms 114640 KB Output is correct
23 Correct 110 ms 114516 KB Output is correct
24 Correct 128 ms 116296 KB Output is correct
25 Correct 220 ms 142792 KB Output is correct
26 Correct 357 ms 181612 KB Output is correct
27 Correct 581 ms 239916 KB Output is correct
28 Runtime error 638 ms 262144 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 94284 KB Output is correct
2 Correct 57 ms 94380 KB Output is correct
3 Correct 55 ms 94344 KB Output is correct
4 Correct 53 ms 94356 KB Output is correct
5 Correct 49 ms 94412 KB Output is correct
6 Correct 53 ms 94556 KB Output is correct
7 Correct 50 ms 94740 KB Output is correct
8 Correct 49 ms 94984 KB Output is correct
9 Correct 50 ms 95180 KB Output is correct
10 Correct 49 ms 94888 KB Output is correct
11 Correct 51 ms 94872 KB Output is correct
12 Correct 52 ms 94928 KB Output is correct
13 Correct 51 ms 94912 KB Output is correct
14 Correct 48 ms 94308 KB Output is correct
15 Correct 47 ms 94260 KB Output is correct
16 Correct 48 ms 94332 KB Output is correct
17 Correct 49 ms 94312 KB Output is correct
18 Correct 51 ms 94396 KB Output is correct
19 Correct 51 ms 94668 KB Output is correct
20 Correct 54 ms 94792 KB Output is correct
21 Correct 50 ms 95052 KB Output is correct
22 Correct 57 ms 95156 KB Output is correct
23 Correct 50 ms 94948 KB Output is correct
24 Correct 53 ms 94972 KB Output is correct
25 Correct 49 ms 94924 KB Output is correct
26 Correct 50 ms 94988 KB Output is correct
27 Correct 52 ms 94276 KB Output is correct
28 Correct 47 ms 94412 KB Output is correct
29 Correct 55 ms 94652 KB Output is correct
30 Correct 53 ms 95536 KB Output is correct
31 Correct 52 ms 95300 KB Output is correct
32 Correct 52 ms 95256 KB Output is correct
33 Correct 53 ms 94924 KB Output is correct
34 Correct 50 ms 95068 KB Output is correct
35 Correct 48 ms 94772 KB Output is correct
36 Correct 51 ms 94668 KB Output is correct
37 Correct 49 ms 95212 KB Output is correct
38 Correct 54 ms 96044 KB Output is correct
39 Correct 86 ms 102756 KB Output is correct
40 Correct 85 ms 105828 KB Output is correct
41 Correct 119 ms 115512 KB Output is correct
42 Correct 108 ms 113444 KB Output is correct
43 Correct 111 ms 113356 KB Output is correct
44 Correct 111 ms 113572 KB Output is correct
45 Correct 125 ms 114584 KB Output is correct
46 Correct 132 ms 114576 KB Output is correct
47 Correct 116 ms 116204 KB Output is correct
48 Correct 211 ms 142724 KB Output is correct
49 Correct 359 ms 181672 KB Output is correct
50 Correct 611 ms 240088 KB Output is correct
51 Runtime error 648 ms 262144 KB Execution killed with signal 9
52 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 94292 KB Output is correct
2 Correct 51 ms 94384 KB Output is correct
3 Correct 48 ms 94392 KB Output is correct
4 Correct 48 ms 94296 KB Output is correct
5 Correct 46 ms 94412 KB Output is correct
6 Correct 48 ms 94564 KB Output is correct
7 Correct 49 ms 94708 KB Output is correct
8 Correct 49 ms 94920 KB Output is correct
9 Correct 51 ms 95180 KB Output is correct
10 Correct 57 ms 94888 KB Output is correct
11 Correct 55 ms 94948 KB Output is correct
12 Correct 49 ms 94920 KB Output is correct
13 Correct 48 ms 94924 KB Output is correct
14 Correct 46 ms 94416 KB Output is correct
15 Correct 55 ms 94444 KB Output is correct
16 Correct 50 ms 94660 KB Output is correct
17 Correct 50 ms 95564 KB Output is correct
18 Correct 50 ms 95304 KB Output is correct
19 Correct 50 ms 95284 KB Output is correct
20 Correct 49 ms 94992 KB Output is correct
21 Correct 57 ms 94840 KB Output is correct
22 Correct 50 ms 94728 KB Output is correct
23 Correct 51 ms 94752 KB Output is correct
24 Correct 55 ms 95184 KB Output is correct
25 Correct 53 ms 96044 KB Output is correct
26 Correct 73 ms 102712 KB Output is correct
27 Correct 83 ms 105808 KB Output is correct
28 Correct 121 ms 115496 KB Output is correct
29 Correct 109 ms 113488 KB Output is correct
30 Correct 116 ms 113456 KB Output is correct
31 Correct 113 ms 113616 KB Output is correct
32 Correct 112 ms 114592 KB Output is correct
33 Correct 118 ms 114484 KB Output is correct
34 Correct 120 ms 116316 KB Output is correct
35 Correct 215 ms 142824 KB Output is correct
36 Correct 364 ms 181580 KB Output is correct
37 Correct 597 ms 239988 KB Output is correct
38 Runtime error 649 ms 262144 KB Execution killed with signal 9
39 Halted 0 ms 0 KB -