oj.uz

Submission #634102

# Submission time Handle Problem Language Result Execution time Memory
634102 2022-08-23T19:56:23 Z tvladm2009 Bali Sculptures (APIO15_sculpture) C++14
25 / 100
 697 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() {
    cin >> n >> a >> b;
    for (int i = 1; i <= n; i++) {
        cin >> y[i];
        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 < 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


*/

Compilation message

sculpture.cpp: In function 'int main()':
sculpture.cpp:35:35: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |                 for (int l = 0; l < dp[k - 1][j - 1].size(); l++) {
      |                                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 94276 KB Output is correct
2 Correct 43 ms 94260 KB Output is correct
3 Correct 45 ms 94264 KB Output is correct
4 Correct 46 ms 94320 KB Output is correct
5 Correct 44 ms 94420 KB Output is correct
6 Correct 43 ms 94540 KB Output is correct
7 Correct 45 ms 94784 KB Output is correct
8 Correct 46 ms 94856 KB Output is correct
9 Correct 46 ms 95128 KB Output is correct
10 Correct 46 ms 94928 KB Output is correct
11 Correct 45 ms 94948 KB Output is correct
12 Correct 45 ms 94904 KB Output is correct
13 Correct 46 ms 94900 KB Output is correct
14 Correct 45 ms 94300 KB Output is correct
15 Correct 47 ms 94244 KB Output is correct
16 Correct 50 ms 94256 KB Output is correct
17 Correct 44 ms 94424 KB Output is correct
18 Correct 45 ms 94368 KB Output is correct
19 Correct 46 ms 94576 KB Output is correct
20 Correct 50 ms 94796 KB Output is correct
21 Correct 46 ms 95176 KB Output is correct
22 Correct 54 ms 95232 KB Output is correct
23 Correct 50 ms 94964 KB Output is correct
24 Correct 46 ms 94968 KB Output is correct
25 Correct 53 ms 94956 KB Output is correct
26 Correct 45 ms 95012 KB Output is correct
27 Correct 44 ms 94360 KB Output is correct
28 Correct 45 ms 94496 KB Output is correct
29 Correct 48 ms 94952 KB Output is correct
30 Correct 78 ms 100676 KB Output is correct
31 Correct 50 ms 95788 KB Output is correct
32 Correct 50 ms 95736 KB Output is correct
33 Correct 45 ms 94960 KB Output is correct
34 Correct 45 ms 94908 KB Output is correct
35 Correct 45 ms 94760 KB Output is correct
36 Correct 46 ms 94644 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 94340 KB Output is correct
2 Correct 50 ms 94284 KB Output is correct
3 Correct 45 ms 94264 KB Output is correct
4 Correct 48 ms 94260 KB Output is correct
5 Correct 43 ms 94336 KB Output is correct
6 Correct 45 ms 94544 KB Output is correct
7 Correct 54 ms 94684 KB Output is correct
8 Correct 47 ms 94892 KB Output is correct
9 Correct 47 ms 95196 KB Output is correct
10 Correct 46 ms 94876 KB Output is correct
11 Correct 51 ms 94936 KB Output is correct
12 Correct 47 ms 94952 KB Output is correct
13 Correct 47 ms 95012 KB Output is correct
14 Correct 49 ms 94284 KB Output is correct
15 Correct 52 ms 94332 KB Output is correct
16 Correct 45 ms 94280 KB Output is correct
17 Correct 45 ms 94264 KB Output is correct
18 Correct 45 ms 94424 KB Output is correct
19 Correct 53 ms 94504 KB Output is correct
20 Correct 45 ms 94712 KB Output is correct
21 Correct 53 ms 95052 KB Output is correct
22 Correct 49 ms 95212 KB Output is correct
23 Correct 49 ms 95072 KB Output is correct
24 Correct 46 ms 94924 KB Output is correct
25 Correct 46 ms 94956 KB Output is correct
26 Correct 54 ms 95052 KB Output is correct
27 Correct 49 ms 95216 KB Output is correct
28 Correct 50 ms 96072 KB Output is correct
29 Correct 79 ms 104752 KB Output is correct
30 Correct 93 ms 108700 KB Output is correct
31 Correct 188 ms 135488 KB Output is correct
32 Correct 139 ms 120444 KB Output is correct
33 Correct 132 ms 120372 KB Output is correct
34 Correct 139 ms 122076 KB Output is correct
35 Correct 149 ms 125660 KB Output is correct
36 Correct 148 ms 126280 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 94340 KB Output is correct
2 Correct 43 ms 94248 KB Output is correct
3 Correct 43 ms 94280 KB Output is correct
4 Correct 45 ms 94252 KB Output is correct
5 Correct 51 ms 94292 KB Output is correct
6 Correct 46 ms 94540 KB Output is correct
7 Correct 46 ms 94736 KB Output is correct
8 Correct 50 ms 94912 KB Output is correct
9 Correct 46 ms 95180 KB Output is correct
10 Correct 46 ms 94924 KB Output is correct
11 Correct 45 ms 94880 KB Output is correct
12 Correct 50 ms 95088 KB Output is correct
13 Correct 57 ms 94960 KB Output is correct
14 Correct 47 ms 95212 KB Output is correct
15 Correct 48 ms 96108 KB Output is correct
16 Correct 77 ms 104688 KB Output is correct
17 Correct 93 ms 108644 KB Output is correct
18 Correct 193 ms 135504 KB Output is correct
19 Correct 132 ms 120424 KB Output is correct
20 Correct 130 ms 120416 KB Output is correct
21 Correct 137 ms 122016 KB Output is correct
22 Correct 151 ms 125612 KB Output is correct
23 Correct 151 ms 126220 KB Output is correct
24 Correct 209 ms 137804 KB Output is correct
25 Correct 504 ms 210784 KB Output is correct
26 Runtime error 695 ms 262144 KB Execution killed with signal 9
27 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 94348 KB Output is correct
2 Correct 46 ms 94352 KB Output is correct
3 Correct 45 ms 94220 KB Output is correct
4 Correct 48 ms 94284 KB Output is correct
5 Correct 48 ms 94356 KB Output is correct
6 Correct 49 ms 94508 KB Output is correct
7 Correct 49 ms 94648 KB Output is correct
8 Correct 46 ms 94960 KB Output is correct
9 Correct 47 ms 95180 KB Output is correct
10 Correct 46 ms 94924 KB Output is correct
11 Correct 45 ms 94852 KB Output is correct
12 Correct 49 ms 94996 KB Output is correct
13 Correct 47 ms 94940 KB Output is correct
14 Correct 43 ms 94248 KB Output is correct
15 Correct 44 ms 94248 KB Output is correct
16 Correct 44 ms 94316 KB Output is correct
17 Correct 44 ms 94264 KB Output is correct
18 Correct 44 ms 94324 KB Output is correct
19 Correct 45 ms 94624 KB Output is correct
20 Correct 48 ms 94744 KB Output is correct
21 Correct 51 ms 95080 KB Output is correct
22 Correct 47 ms 95180 KB Output is correct
23 Correct 46 ms 94944 KB Output is correct
24 Correct 46 ms 94884 KB Output is correct
25 Correct 46 ms 94992 KB Output is correct
26 Correct 46 ms 94984 KB Output is correct
27 Correct 46 ms 94352 KB Output is correct
28 Correct 45 ms 94456 KB Output is correct
29 Correct 51 ms 94944 KB Output is correct
30 Correct 72 ms 100680 KB Output is correct
31 Correct 50 ms 95652 KB Output is correct
32 Correct 49 ms 95688 KB Output is correct
33 Correct 46 ms 94996 KB Output is correct
34 Correct 48 ms 94924 KB Output is correct
35 Correct 53 ms 94668 KB Output is correct
36 Correct 53 ms 94648 KB Output is correct
37 Correct 51 ms 95208 KB Output is correct
38 Correct 50 ms 96128 KB Output is correct
39 Correct 86 ms 104768 KB Output is correct
40 Correct 89 ms 108604 KB Output is correct
41 Correct 201 ms 135472 KB Output is correct
42 Correct 134 ms 120396 KB Output is correct
43 Correct 132 ms 120404 KB Output is correct
44 Correct 138 ms 121932 KB Output is correct
45 Correct 150 ms 125680 KB Output is correct
46 Correct 149 ms 126152 KB Output is correct
47 Correct 213 ms 137744 KB Output is correct
48 Correct 493 ms 210808 KB Output is correct
49 Runtime error 692 ms 262144 KB Execution killed with signal 9
50 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 94284 KB Output is correct
2 Correct 43 ms 94268 KB Output is correct
3 Correct 44 ms 94328 KB Output is correct
4 Correct 45 ms 94336 KB Output is correct
5 Correct 50 ms 94276 KB Output is correct
6 Correct 54 ms 94540 KB Output is correct
7 Correct 50 ms 94780 KB Output is correct
8 Correct 45 ms 94924 KB Output is correct
9 Correct 47 ms 95208 KB Output is correct
10 Correct 45 ms 94920 KB Output is correct
11 Correct 45 ms 94924 KB Output is correct
12 Correct 47 ms 94940 KB Output is correct
13 Correct 48 ms 95012 KB Output is correct
14 Correct 51 ms 94312 KB Output is correct
15 Correct 45 ms 94484 KB Output is correct
16 Correct 45 ms 95000 KB Output is correct
17 Correct 83 ms 100636 KB Output is correct
18 Correct 54 ms 95740 KB Output is correct
19 Correct 59 ms 95724 KB Output is correct
20 Correct 46 ms 94904 KB Output is correct
21 Correct 45 ms 94924 KB Output is correct
22 Correct 44 ms 94696 KB Output is correct
23 Correct 44 ms 94756 KB Output is correct
24 Correct 47 ms 95204 KB Output is correct
25 Correct 52 ms 96056 KB Output is correct
26 Correct 82 ms 104704 KB Output is correct
27 Correct 90 ms 108544 KB Output is correct
28 Correct 196 ms 135528 KB Output is correct
29 Correct 135 ms 120416 KB Output is correct
30 Correct 146 ms 120356 KB Output is correct
31 Correct 141 ms 121952 KB Output is correct
32 Correct 159 ms 125588 KB Output is correct
33 Correct 151 ms 126156 KB Output is correct
34 Correct 203 ms 137928 KB Output is correct
35 Correct 502 ms 210908 KB Output is correct
36 Runtime error 697 ms 262144 KB Execution killed with signal 9
37 Halted 0 ms 0 KB -