oj.uz

Submission #634653

# Submission time Handle Problem Language Result Execution time Memory
634653 2022-08-24T16:28:54 Z tvladm2009 Bali Sculptures (APIO15_sculpture) C++14
25 / 100
 734 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++) {
                if (n < 100) {
                    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]);
                    }
                } else {
                    for (int l = 0; l < min(2LL, (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 94380 KB Output is correct
2 Correct 46 ms 94264 KB Output is correct
3 Correct 45 ms 94344 KB Output is correct
4 Correct 45 ms 94272 KB Output is correct
5 Correct 47 ms 94416 KB Output is correct
6 Correct 50 ms 94536 KB Output is correct
7 Correct 48 ms 94728 KB Output is correct
8 Correct 52 ms 94924 KB Output is correct
9 Correct 51 ms 95196 KB Output is correct
10 Correct 60 ms 94924 KB Output is correct
11 Correct 53 ms 94932 KB Output is correct
12 Correct 51 ms 94952 KB Output is correct
13 Correct 50 ms 95004 KB Output is correct
14 Correct 48 ms 94408 KB Output is correct
15 Correct 48 ms 94316 KB Output is correct
16 Correct 51 ms 94288 KB Output is correct
17 Correct 48 ms 94260 KB Output is correct
18 Correct 51 ms 94420 KB Output is correct
19 Correct 51 ms 94540 KB Output is correct
20 Correct 49 ms 94764 KB Output is correct
21 Correct 49 ms 95164 KB Output is correct
22 Correct 50 ms 95268 KB Output is correct
23 Correct 49 ms 94964 KB Output is correct
24 Correct 48 ms 94896 KB Output is correct
25 Correct 50 ms 95016 KB Output is correct
26 Correct 54 ms 95052 KB Output is correct
27 Correct 48 ms 94356 KB Output is correct
28 Correct 49 ms 94432 KB Output is correct
29 Correct 48 ms 94692 KB Output is correct
30 Correct 53 ms 96232 KB Output is correct
31 Correct 53 ms 95448 KB Output is correct
32 Correct 53 ms 95528 KB Output is correct
33 Correct 59 ms 94872 KB Output is correct
34 Correct 55 ms 94908 KB Output is correct
35 Correct 55 ms 94668 KB Output is correct
36 Correct 48 ms 94744 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 94272 KB Output is correct
2 Correct 55 ms 94284 KB Output is correct
3 Correct 47 ms 94344 KB Output is correct
4 Correct 50 ms 94316 KB Output is correct
5 Correct 48 ms 94380 KB Output is correct
6 Correct 50 ms 94624 KB Output is correct
7 Correct 49 ms 94784 KB Output is correct
8 Correct 50 ms 94912 KB Output is correct
9 Correct 50 ms 95128 KB Output is correct
10 Correct 49 ms 94904 KB Output is correct
11 Correct 47 ms 94948 KB Output is correct
12 Correct 48 ms 94948 KB Output is correct
13 Correct 48 ms 94924 KB Output is correct
14 Correct 45 ms 94252 KB Output is correct
15 Correct 46 ms 94284 KB Output is correct
16 Correct 47 ms 94272 KB Output is correct
17 Correct 48 ms 94336 KB Output is correct
18 Correct 48 ms 94440 KB Output is correct
19 Correct 47 ms 94560 KB Output is correct
20 Correct 47 ms 94836 KB Output is correct
21 Correct 49 ms 95176 KB Output is correct
22 Correct 51 ms 95224 KB Output is correct
23 Correct 47 ms 94868 KB Output is correct
24 Correct 48 ms 94932 KB Output is correct
25 Correct 50 ms 94924 KB Output is correct
26 Correct 48 ms 95000 KB Output is correct
27 Correct 48 ms 95180 KB Output is correct
28 Correct 55 ms 96204 KB Output is correct
29 Correct 88 ms 104268 KB Output is correct
30 Correct 97 ms 108060 KB Output is correct
31 Correct 158 ms 126244 KB Output is correct
32 Correct 132 ms 119168 KB Output is correct
33 Correct 138 ms 119168 KB Output is correct
34 Correct 146 ms 120076 KB Output is correct
35 Correct 147 ms 122140 KB Output is correct
36 Correct 140 ms 122852 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 94256 KB Output is correct
2 Correct 46 ms 94356 KB Output is correct
3 Correct 53 ms 94468 KB Output is correct
4 Correct 54 ms 94280 KB Output is correct
5 Correct 51 ms 94412 KB Output is correct
6 Correct 49 ms 94560 KB Output is correct
7 Correct 47 ms 94764 KB Output is correct
8 Correct 48 ms 94876 KB Output is correct
9 Correct 54 ms 95320 KB Output is correct
10 Correct 47 ms 94964 KB Output is correct
11 Correct 49 ms 94992 KB Output is correct
12 Correct 50 ms 94980 KB Output is correct
13 Correct 53 ms 94972 KB Output is correct
14 Correct 48 ms 95180 KB Output is correct
15 Correct 52 ms 96116 KB Output is correct
16 Correct 85 ms 104292 KB Output is correct
17 Correct 92 ms 108040 KB Output is correct
18 Correct 159 ms 126284 KB Output is correct
19 Correct 139 ms 119088 KB Output is correct
20 Correct 134 ms 119080 KB Output is correct
21 Correct 133 ms 119980 KB Output is correct
22 Correct 149 ms 122084 KB Output is correct
23 Correct 144 ms 122976 KB Output is correct
24 Correct 165 ms 126200 KB Output is correct
25 Correct 326 ms 168228 KB Output is correct
26 Correct 616 ms 236264 KB Output is correct
27 Runtime error 696 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 48 ms 94284 KB Output is correct
2 Correct 48 ms 94356 KB Output is correct
3 Correct 46 ms 94284 KB Output is correct
4 Correct 46 ms 94276 KB Output is correct
5 Correct 46 ms 94416 KB Output is correct
6 Correct 49 ms 94556 KB Output is correct
7 Correct 57 ms 94696 KB Output is correct
8 Correct 50 ms 94924 KB Output is correct
9 Correct 56 ms 95180 KB Output is correct
10 Correct 46 ms 94884 KB Output is correct
11 Correct 47 ms 94928 KB Output is correct
12 Correct 53 ms 94864 KB Output is correct
13 Correct 50 ms 94908 KB Output is correct
14 Correct 48 ms 94264 KB Output is correct
15 Correct 47 ms 94372 KB Output is correct
16 Correct 45 ms 94292 KB Output is correct
17 Correct 47 ms 94240 KB Output is correct
18 Correct 45 ms 94304 KB Output is correct
19 Correct 47 ms 94608 KB Output is correct
20 Correct 46 ms 94752 KB Output is correct
21 Correct 50 ms 95096 KB Output is correct
22 Correct 50 ms 95300 KB Output is correct
23 Correct 49 ms 95000 KB Output is correct
24 Correct 48 ms 94976 KB Output is correct
25 Correct 55 ms 95140 KB Output is correct
26 Correct 49 ms 95052 KB Output is correct
27 Correct 46 ms 94364 KB Output is correct
28 Correct 50 ms 94412 KB Output is correct
29 Correct 52 ms 94640 KB Output is correct
30 Correct 55 ms 96204 KB Output is correct
31 Correct 50 ms 95436 KB Output is correct
32 Correct 52 ms 95636 KB Output is correct
33 Correct 48 ms 94932 KB Output is correct
34 Correct 51 ms 94948 KB Output is correct
35 Correct 51 ms 94688 KB Output is correct
36 Correct 53 ms 94716 KB Output is correct
37 Correct 55 ms 95184 KB Output is correct
38 Correct 51 ms 96084 KB Output is correct
39 Correct 79 ms 104260 KB Output is correct
40 Correct 91 ms 108080 KB Output is correct
41 Correct 187 ms 126284 KB Output is correct
42 Correct 136 ms 119140 KB Output is correct
43 Correct 132 ms 119104 KB Output is correct
44 Correct 133 ms 120056 KB Output is correct
45 Correct 146 ms 122076 KB Output is correct
46 Correct 144 ms 122920 KB Output is correct
47 Correct 163 ms 126172 KB Output is correct
48 Correct 333 ms 168240 KB Output is correct
49 Correct 610 ms 236328 KB Output is correct
50 Runtime error 670 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 46 ms 94336 KB Output is correct
2 Correct 47 ms 94360 KB Output is correct
3 Correct 46 ms 94276 KB Output is correct
4 Correct 48 ms 94372 KB Output is correct
5 Correct 56 ms 94376 KB Output is correct
6 Correct 47 ms 94548 KB Output is correct
7 Correct 47 ms 94776 KB Output is correct
8 Correct 48 ms 94980 KB Output is correct
9 Correct 48 ms 95140 KB Output is correct
10 Correct 48 ms 94872 KB Output is correct
11 Correct 49 ms 94960 KB Output is correct
12 Correct 49 ms 94940 KB Output is correct
13 Correct 49 ms 94972 KB Output is correct
14 Correct 46 ms 94324 KB Output is correct
15 Correct 46 ms 94412 KB Output is correct
16 Correct 47 ms 94704 KB Output is correct
17 Correct 54 ms 96248 KB Output is correct
18 Correct 54 ms 95480 KB Output is correct
19 Correct 52 ms 95480 KB Output is correct
20 Correct 54 ms 95084 KB Output is correct
21 Correct 49 ms 94896 KB Output is correct
22 Correct 51 ms 94704 KB Output is correct
23 Correct 47 ms 94744 KB Output is correct
24 Correct 48 ms 95160 KB Output is correct
25 Correct 52 ms 96168 KB Output is correct
26 Correct 80 ms 104488 KB Output is correct
27 Correct 92 ms 108004 KB Output is correct
28 Correct 163 ms 126268 KB Output is correct
29 Correct 134 ms 119060 KB Output is correct
30 Correct 132 ms 119132 KB Output is correct
31 Correct 135 ms 119952 KB Output is correct
32 Correct 142 ms 122172 KB Output is correct
33 Correct 169 ms 122980 KB Output is correct
34 Correct 157 ms 126192 KB Output is correct
35 Correct 345 ms 168252 KB Output is correct
36 Correct 734 ms 236364 KB Output is correct
37 Runtime error 657 ms 262144 KB Execution killed with signal 9
38 Halted 0 ms 0 KB -