oj.uz

Submission #634652

# Submission time Handle Problem Language Result Execution time Memory
634652 2022-08-24T16:26:52 Z tvladm2009 Bali Sculptures (APIO15_sculpture) C++14
25 / 100
 783 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(10LL, (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 46 ms 94280 KB Output is correct
2 Correct 45 ms 94328 KB Output is correct
3 Correct 47 ms 94232 KB Output is correct
4 Correct 47 ms 94352 KB Output is correct
5 Correct 54 ms 94412 KB Output is correct
6 Correct 49 ms 94540 KB Output is correct
7 Correct 48 ms 94728 KB Output is correct
8 Correct 47 ms 94852 KB Output is correct
9 Correct 49 ms 95176 KB Output is correct
10 Correct 48 ms 94924 KB Output is correct
11 Correct 55 ms 95024 KB Output is correct
12 Correct 52 ms 94936 KB Output is correct
13 Correct 51 ms 95008 KB Output is correct
14 Correct 48 ms 94264 KB Output is correct
15 Correct 47 ms 94288 KB Output is correct
16 Correct 46 ms 94240 KB Output is correct
17 Correct 50 ms 94268 KB Output is correct
18 Correct 55 ms 94540 KB Output is correct
19 Correct 57 ms 94552 KB Output is correct
20 Correct 53 ms 94780 KB Output is correct
21 Correct 49 ms 95108 KB Output is correct
22 Correct 48 ms 95276 KB Output is correct
23 Correct 50 ms 94960 KB Output is correct
24 Correct 52 ms 94924 KB Output is correct
25 Correct 49 ms 94972 KB Output is correct
26 Correct 56 ms 95052 KB Output is correct
27 Correct 46 ms 94284 KB Output is correct
28 Correct 53 ms 94416 KB Output is correct
29 Correct 48 ms 94672 KB Output is correct
30 Correct 57 ms 96248 KB Output is correct
31 Correct 50 ms 95528 KB Output is correct
32 Correct 58 ms 95496 KB Output is correct
33 Correct 50 ms 95000 KB Output is correct
34 Correct 48 ms 94960 KB Output is correct
35 Correct 47 ms 94680 KB Output is correct
36 Correct 47 ms 94748 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 94368 KB Output is correct
2 Correct 53 ms 94264 KB Output is correct
3 Correct 46 ms 94284 KB Output is correct
4 Correct 47 ms 94252 KB Output is correct
5 Correct 46 ms 94352 KB Output is correct
6 Correct 49 ms 94512 KB Output is correct
7 Correct 49 ms 94720 KB Output is correct
8 Correct 50 ms 94972 KB Output is correct
9 Correct 52 ms 95228 KB Output is correct
10 Correct 47 ms 94924 KB Output is correct
11 Correct 50 ms 94980 KB Output is correct
12 Correct 49 ms 94996 KB Output is correct
13 Correct 52 ms 95012 KB Output is correct
14 Correct 48 ms 94348 KB Output is correct
15 Correct 47 ms 94312 KB Output is correct
16 Correct 46 ms 94292 KB Output is correct
17 Correct 46 ms 94356 KB Output is correct
18 Correct 47 ms 94372 KB Output is correct
19 Correct 47 ms 94596 KB Output is correct
20 Correct 48 ms 94712 KB Output is correct
21 Correct 49 ms 95148 KB Output is correct
22 Correct 50 ms 95200 KB Output is correct
23 Correct 49 ms 94884 KB Output is correct
24 Correct 52 ms 94912 KB Output is correct
25 Correct 49 ms 94928 KB Output is correct
26 Correct 48 ms 95068 KB Output is correct
27 Correct 49 ms 95180 KB Output is correct
28 Correct 54 ms 96076 KB Output is correct
29 Correct 81 ms 104268 KB Output is correct
30 Correct 99 ms 107988 KB Output is correct
31 Correct 162 ms 126304 KB Output is correct
32 Correct 128 ms 119112 KB Output is correct
33 Correct 132 ms 119084 KB Output is correct
34 Correct 132 ms 120016 KB Output is correct
35 Correct 167 ms 122180 KB Output is correct
36 Correct 167 ms 122968 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 94284 KB Output is correct
2 Correct 46 ms 94292 KB Output is correct
3 Correct 46 ms 94228 KB Output is correct
4 Correct 46 ms 94312 KB Output is correct
5 Correct 46 ms 94464 KB Output is correct
6 Correct 52 ms 94500 KB Output is correct
7 Correct 48 ms 94792 KB Output is correct
8 Correct 58 ms 94944 KB Output is correct
9 Correct 52 ms 95192 KB Output is correct
10 Correct 48 ms 94924 KB Output is correct
11 Correct 48 ms 94924 KB Output is correct
12 Correct 48 ms 94924 KB Output is correct
13 Correct 48 ms 95024 KB Output is correct
14 Correct 53 ms 95208 KB Output is correct
15 Correct 52 ms 96084 KB Output is correct
16 Correct 83 ms 104336 KB Output is correct
17 Correct 95 ms 108020 KB Output is correct
18 Correct 159 ms 126312 KB Output is correct
19 Correct 139 ms 119228 KB Output is correct
20 Correct 138 ms 119176 KB Output is correct
21 Correct 132 ms 120064 KB Output is correct
22 Correct 148 ms 122204 KB Output is correct
23 Correct 155 ms 122956 KB Output is correct
24 Correct 166 ms 126200 KB Output is correct
25 Correct 313 ms 168168 KB Output is correct
26 Correct 603 ms 236324 KB Output is correct
27 Runtime error 659 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 52 ms 94284 KB Output is correct
2 Correct 48 ms 94284 KB Output is correct
3 Correct 44 ms 94284 KB Output is correct
4 Correct 45 ms 94308 KB Output is correct
5 Correct 47 ms 94444 KB Output is correct
6 Correct 51 ms 94556 KB Output is correct
7 Correct 50 ms 94788 KB Output is correct
8 Correct 49 ms 94908 KB Output is correct
9 Correct 59 ms 95148 KB Output is correct
10 Correct 50 ms 94980 KB Output is correct
11 Correct 53 ms 94868 KB Output is correct
12 Correct 47 ms 94924 KB Output is correct
13 Correct 57 ms 94972 KB Output is correct
14 Correct 52 ms 94288 KB Output is correct
15 Correct 48 ms 94280 KB Output is correct
16 Correct 47 ms 94368 KB Output is correct
17 Correct 53 ms 94264 KB Output is correct
18 Correct 49 ms 94416 KB Output is correct
19 Correct 49 ms 94548 KB Output is correct
20 Correct 54 ms 94816 KB Output is correct
21 Correct 51 ms 95124 KB Output is correct
22 Correct 55 ms 95248 KB Output is correct
23 Correct 50 ms 94900 KB Output is correct
24 Correct 49 ms 94964 KB Output is correct
25 Correct 50 ms 94960 KB Output is correct
26 Correct 51 ms 95068 KB Output is correct
27 Correct 47 ms 94284 KB Output is correct
28 Correct 48 ms 94424 KB Output is correct
29 Correct 49 ms 94804 KB Output is correct
30 Correct 55 ms 96168 KB Output is correct
31 Correct 52 ms 95436 KB Output is correct
32 Correct 50 ms 95488 KB Output is correct
33 Correct 47 ms 94904 KB Output is correct
34 Correct 47 ms 94964 KB Output is correct
35 Correct 48 ms 94756 KB Output is correct
36 Correct 47 ms 94728 KB Output is correct
37 Correct 48 ms 95216 KB Output is correct
38 Correct 53 ms 96256 KB Output is correct
39 Correct 81 ms 104324 KB Output is correct
40 Correct 93 ms 108036 KB Output is correct
41 Correct 175 ms 126328 KB Output is correct
42 Correct 132 ms 119156 KB Output is correct
43 Correct 131 ms 119160 KB Output is correct
44 Correct 148 ms 120004 KB Output is correct
45 Correct 147 ms 122136 KB Output is correct
46 Correct 147 ms 122964 KB Output is correct
47 Correct 162 ms 126372 KB Output is correct
48 Correct 348 ms 168244 KB Output is correct
49 Correct 593 ms 236432 KB Output is correct
50 Runtime error 783 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 50 ms 94368 KB Output is correct
2 Correct 46 ms 94336 KB Output is correct
3 Correct 49 ms 94292 KB Output is correct
4 Correct 49 ms 94328 KB Output is correct
5 Correct 52 ms 94336 KB Output is correct
6 Correct 49 ms 94564 KB Output is correct
7 Correct 52 ms 94692 KB Output is correct
8 Correct 49 ms 94924 KB Output is correct
9 Correct 50 ms 95132 KB Output is correct
10 Correct 55 ms 94928 KB Output is correct
11 Correct 49 ms 94992 KB Output is correct
12 Correct 59 ms 94904 KB Output is correct
13 Correct 50 ms 95020 KB Output is correct
14 Correct 54 ms 94316 KB Output is correct
15 Correct 47 ms 94480 KB Output is correct
16 Correct 49 ms 94668 KB Output is correct
17 Correct 52 ms 96204 KB Output is correct
18 Correct 52 ms 95464 KB Output is correct
19 Correct 52 ms 95508 KB Output is correct
20 Correct 48 ms 94880 KB Output is correct
21 Correct 48 ms 94924 KB Output is correct
22 Correct 47 ms 94656 KB Output is correct
23 Correct 47 ms 94676 KB Output is correct
24 Correct 52 ms 95232 KB Output is correct
25 Correct 57 ms 96076 KB Output is correct
26 Correct 84 ms 104352 KB Output is correct
27 Correct 93 ms 107972 KB Output is correct
28 Correct 158 ms 126284 KB Output is correct
29 Correct 134 ms 119108 KB Output is correct
30 Correct 132 ms 119068 KB Output is correct
31 Correct 166 ms 120060 KB Output is correct
32 Correct 143 ms 122200 KB Output is correct
33 Correct 142 ms 122980 KB Output is correct
34 Correct 164 ms 126128 KB Output is correct
35 Correct 333 ms 168264 KB Output is correct
36 Correct 592 ms 236300 KB Output is correct
37 Runtime error 690 ms 262144 KB Execution killed with signal 9
38 Halted 0 ms 0 KB -