oj.uz

Submission #634647

# Submission time Handle Problem Language Result Execution time Memory
634647 2022-08-24T16:22:02 Z tvladm2009 Bali Sculptures (APIO15_sculpture) C++14
25 / 100
 681 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(100LL, (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());
            while (dp[i][j].size() > 100) {
                dp[i][j].pop_back();
            }
        }
    }
    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 44 ms 94372 KB Output is correct
2 Correct 46 ms 94384 KB Output is correct
3 Correct 48 ms 94256 KB Output is correct
4 Correct 48 ms 94340 KB Output is correct
5 Correct 49 ms 94484 KB Output is correct
6 Correct 45 ms 94532 KB Output is correct
7 Correct 46 ms 94700 KB Output is correct
8 Correct 46 ms 94860 KB Output is correct
9 Correct 47 ms 95144 KB Output is correct
10 Correct 50 ms 94880 KB Output is correct
11 Correct 49 ms 94972 KB Output is correct
12 Correct 52 ms 94952 KB Output is correct
13 Correct 49 ms 94980 KB Output is correct
14 Correct 45 ms 94284 KB Output is correct
15 Correct 44 ms 94256 KB Output is correct
16 Correct 47 ms 94280 KB Output is correct
17 Correct 45 ms 94340 KB Output is correct
18 Correct 46 ms 94316 KB Output is correct
19 Correct 46 ms 94560 KB Output is correct
20 Correct 50 ms 94780 KB Output is correct
21 Correct 49 ms 95052 KB Output is correct
22 Correct 52 ms 95392 KB Output is correct
23 Correct 54 ms 94912 KB Output is correct
24 Correct 55 ms 94908 KB Output is correct
25 Correct 57 ms 95024 KB Output is correct
26 Correct 49 ms 95072 KB Output is correct
27 Correct 46 ms 94360 KB Output is correct
28 Correct 46 ms 94448 KB Output is correct
29 Correct 47 ms 94708 KB Output is correct
30 Correct 54 ms 96152 KB Output is correct
31 Correct 58 ms 95464 KB Output is correct
32 Correct 53 ms 95436 KB Output is correct
33 Correct 51 ms 94932 KB Output is correct
34 Correct 47 ms 94896 KB Output is correct
35 Correct 46 ms 94716 KB Output is correct
36 Correct 48 ms 94760 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 94336 KB Output is correct
2 Correct 45 ms 94364 KB Output is correct
3 Correct 45 ms 94284 KB Output is correct
4 Correct 47 ms 94364 KB Output is correct
5 Correct 47 ms 94420 KB Output is correct
6 Correct 47 ms 94468 KB Output is correct
7 Correct 47 ms 94820 KB Output is correct
8 Correct 49 ms 94872 KB Output is correct
9 Correct 49 ms 95192 KB Output is correct
10 Correct 47 ms 94956 KB Output is correct
11 Correct 55 ms 94928 KB Output is correct
12 Correct 51 ms 94924 KB Output is correct
13 Correct 49 ms 95012 KB Output is correct
14 Correct 52 ms 94260 KB Output is correct
15 Correct 47 ms 94276 KB Output is correct
16 Correct 46 ms 94356 KB Output is correct
17 Correct 46 ms 94360 KB Output is correct
18 Correct 47 ms 94376 KB Output is correct
19 Correct 47 ms 94548 KB Output is correct
20 Correct 49 ms 94728 KB Output is correct
21 Correct 49 ms 95044 KB Output is correct
22 Correct 49 ms 95244 KB Output is correct
23 Correct 51 ms 95000 KB Output is correct
24 Correct 47 ms 94964 KB Output is correct
25 Correct 48 ms 95008 KB Output is correct
26 Correct 48 ms 95052 KB Output is correct
27 Correct 50 ms 95256 KB Output is correct
28 Correct 53 ms 96088 KB Output is correct
29 Correct 82 ms 104272 KB Output is correct
30 Correct 92 ms 108060 KB Output is correct
31 Correct 153 ms 126348 KB Output is correct
32 Correct 132 ms 119140 KB Output is correct
33 Correct 136 ms 119100 KB Output is correct
34 Correct 139 ms 120120 KB Output is correct
35 Correct 137 ms 122212 KB Output is correct
36 Correct 144 ms 122868 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 94292 KB Output is correct
2 Correct 46 ms 94360 KB Output is correct
3 Correct 47 ms 94284 KB Output is correct
4 Correct 50 ms 94272 KB Output is correct
5 Correct 46 ms 94384 KB Output is correct
6 Correct 56 ms 94504 KB Output is correct
7 Correct 48 ms 94712 KB Output is correct
8 Correct 51 ms 94872 KB Output is correct
9 Correct 48 ms 95188 KB Output is correct
10 Correct 48 ms 94996 KB Output is correct
11 Correct 47 ms 94864 KB Output is correct
12 Correct 48 ms 94880 KB Output is correct
13 Correct 48 ms 94920 KB Output is correct
14 Correct 49 ms 95188 KB Output is correct
15 Correct 52 ms 96132 KB Output is correct
16 Correct 78 ms 104268 KB Output is correct
17 Correct 90 ms 107988 KB Output is correct
18 Correct 160 ms 126340 KB Output is correct
19 Correct 132 ms 119116 KB Output is correct
20 Correct 131 ms 119084 KB Output is correct
21 Correct 134 ms 120060 KB Output is correct
22 Correct 146 ms 122136 KB Output is correct
23 Correct 144 ms 122956 KB Output is correct
24 Correct 158 ms 126120 KB Output is correct
25 Correct 328 ms 168220 KB Output is correct
26 Correct 575 ms 236360 KB Output is correct
27 Runtime error 662 ms 262144 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 94284 KB Output is correct
2 Correct 46 ms 94368 KB Output is correct
3 Correct 46 ms 94232 KB Output is correct
4 Correct 45 ms 94284 KB Output is correct
5 Correct 49 ms 94408 KB Output is correct
6 Correct 52 ms 94556 KB Output is correct
7 Correct 48 ms 94732 KB Output is correct
8 Correct 49 ms 94912 KB Output is correct
9 Correct 49 ms 95220 KB Output is correct
10 Correct 50 ms 94944 KB Output is correct
11 Correct 49 ms 94956 KB Output is correct
12 Correct 51 ms 94916 KB Output is correct
13 Correct 48 ms 95004 KB Output is correct
14 Correct 45 ms 94368 KB Output is correct
15 Correct 45 ms 94360 KB Output is correct
16 Correct 46 ms 94248 KB Output is correct
17 Correct 46 ms 94360 KB Output is correct
18 Correct 48 ms 94412 KB Output is correct
19 Correct 49 ms 94544 KB Output is correct
20 Correct 49 ms 94804 KB Output is correct
21 Correct 49 ms 95048 KB Output is correct
22 Correct 50 ms 95284 KB Output is correct
23 Correct 48 ms 94884 KB Output is correct
24 Correct 55 ms 94912 KB Output is correct
25 Correct 50 ms 94988 KB Output is correct
26 Correct 49 ms 95024 KB Output is correct
27 Correct 46 ms 94284 KB Output is correct
28 Correct 49 ms 94460 KB Output is correct
29 Correct 48 ms 94724 KB Output is correct
30 Correct 54 ms 96200 KB Output is correct
31 Correct 52 ms 95468 KB Output is correct
32 Correct 52 ms 95444 KB Output is correct
33 Correct 50 ms 94976 KB Output is correct
34 Correct 52 ms 94852 KB Output is correct
35 Correct 47 ms 94668 KB Output is correct
36 Correct 49 ms 94696 KB Output is correct
37 Correct 49 ms 95200 KB Output is correct
38 Correct 52 ms 96128 KB Output is correct
39 Correct 82 ms 104396 KB Output is correct
40 Correct 96 ms 108044 KB Output is correct
41 Correct 159 ms 126276 KB Output is correct
42 Correct 132 ms 119072 KB Output is correct
43 Correct 133 ms 119108 KB Output is correct
44 Correct 140 ms 120072 KB Output is correct
45 Correct 147 ms 122212 KB Output is correct
46 Correct 151 ms 122908 KB Output is correct
47 Correct 204 ms 126156 KB Output is correct
48 Correct 339 ms 168256 KB Output is correct
49 Correct 603 ms 236312 KB Output is correct
50 Runtime error 666 ms 262144 KB Execution killed with signal 9
51 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 94284 KB Output is correct
2 Correct 53 ms 94300 KB Output is correct
3 Correct 48 ms 94232 KB Output is correct
4 Correct 48 ms 94256 KB Output is correct
5 Correct 46 ms 94328 KB Output is correct
6 Correct 47 ms 94548 KB Output is correct
7 Correct 48 ms 94716 KB Output is correct
8 Correct 49 ms 94848 KB Output is correct
9 Correct 54 ms 95212 KB Output is correct
10 Correct 49 ms 94888 KB Output is correct
11 Correct 52 ms 94996 KB Output is correct
12 Correct 49 ms 94968 KB Output is correct
13 Correct 48 ms 94924 KB Output is correct
14 Correct 56 ms 94284 KB Output is correct
15 Correct 51 ms 94444 KB Output is correct
16 Correct 50 ms 94696 KB Output is correct
17 Correct 53 ms 96164 KB Output is correct
18 Correct 53 ms 95436 KB Output is correct
19 Correct 52 ms 95436 KB Output is correct
20 Correct 55 ms 95136 KB Output is correct
21 Correct 59 ms 94888 KB Output is correct
22 Correct 48 ms 94656 KB Output is correct
23 Correct 47 ms 94768 KB Output is correct
24 Correct 49 ms 95216 KB Output is correct
25 Correct 54 ms 96160 KB Output is correct
26 Correct 79 ms 104256 KB Output is correct
27 Correct 99 ms 107980 KB Output is correct
28 Correct 166 ms 126260 KB Output is correct
29 Correct 133 ms 119116 KB Output is correct
30 Correct 133 ms 119244 KB Output is correct
31 Correct 136 ms 119984 KB Output is correct
32 Correct 145 ms 122100 KB Output is correct
33 Correct 147 ms 122872 KB Output is correct
34 Correct 187 ms 126148 KB Output is correct
35 Correct 322 ms 168168 KB Output is correct
36 Correct 609 ms 236316 KB Output is correct
37 Runtime error 681 ms 262144 KB Execution killed with signal 9
38 Halted 0 ms 0 KB -