oj.uz

Submission #527574

# Submission time Handle Problem Language Result Execution time Memory
527574 2022-02-17T17:07:12 Z SlavicG Bali Sculptures (APIO15_sculpture) C++17
16 / 100
 822 ms 170460 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()

const int N = 100, K = 2200;
int p[N];
int sum(int l, int r) {
    return p[r] - (l ? p[l - 1] : 0);
}

//dp[index][OR][number of subarrays] = 1 if possible to obtain such partition

int dp[N][K][N];
void solve() { 
    int n, A, B;
    cin >> n >> A >> B;
    vector<int> a(n);
    for(int i = 0;i < n; ++i) {
        cin >> a[i];
        p[i] = (i ? p[i - 1] : 0) + a[i];
    }

    dp[0][0][0] = 1;

    for(int i = 1; i <= n; ++i) {
        for(int j = 0;j < i; ++j) {
            for(int OR = 0; OR < K; ++OR) {
                int s = sum(j, i - 1);
                for(int k = 0; k < B; ++k) {
                    dp[i][OR | s][k + 1] |= dp[j][OR][k]; 
                }
            }
        }
    }
    int ans = INT_MAX;
    for(int i = A; i <= B; ++i) {
        for(int OR = 0; OR < K; ++OR) {
            if(dp[n][OR][i]) ans = min(ans, OR);
        }
    }
    cout << ans << "\n";
} 
 
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t--) {
        solve();
    }
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5452 KB Output is correct
2 Correct 3 ms 7116 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 2 ms 4556 KB Output is correct
5 Correct 4 ms 8944 KB Output is correct
6 Correct 14 ms 13204 KB Output is correct
7 Correct 9 ms 14924 KB Output is correct
8 Correct 12 ms 17484 KB Output is correct
9 Correct 10 ms 17484 KB Output is correct
10 Correct 12 ms 17436 KB Output is correct
11 Correct 10 ms 17484 KB Output is correct
12 Correct 10 ms 17484 KB Output is correct
13 Correct 26 ms 17548 KB Output is correct
14 Correct 3 ms 5452 KB Output is correct
15 Correct 3 ms 5452 KB Output is correct
16 Correct 3 ms 5452 KB Output is correct
17 Correct 2 ms 4556 KB Output is correct
18 Correct 4 ms 8908 KB Output is correct
19 Correct 14 ms 13236 KB Output is correct
20 Correct 8 ms 14924 KB Output is correct
21 Correct 19 ms 17448 KB Output is correct
22 Correct 14 ms 17428 KB Output is correct
23 Correct 14 ms 17488 KB Output is correct
24 Correct 10 ms 17468 KB Output is correct
25 Correct 17 ms 17548 KB Output is correct
26 Correct 22 ms 17460 KB Output is correct
27 Runtime error 2 ms 460 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5396 KB Output is correct
2 Correct 3 ms 7116 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 2 ms 4556 KB Output is correct
5 Correct 4 ms 8908 KB Output is correct
6 Correct 13 ms 13132 KB Output is correct
7 Correct 10 ms 14924 KB Output is correct
8 Correct 10 ms 17516 KB Output is correct
9 Correct 10 ms 17464 KB Output is correct
10 Correct 13 ms 17484 KB Output is correct
11 Correct 10 ms 17436 KB Output is correct
12 Correct 10 ms 17488 KB Output is correct
13 Correct 25 ms 17484 KB Output is correct
14 Correct 3 ms 5436 KB Output is correct
15 Correct 3 ms 5452 KB Output is correct
16 Correct 3 ms 5452 KB Output is correct
17 Correct 2 ms 4556 KB Output is correct
18 Correct 4 ms 8908 KB Output is correct
19 Correct 15 ms 13252 KB Output is correct
20 Correct 8 ms 14924 KB Output is correct
21 Correct 15 ms 17524 KB Output is correct
22 Correct 14 ms 17416 KB Output is correct
23 Correct 15 ms 17412 KB Output is correct
24 Correct 10 ms 17464 KB Output is correct
25 Correct 19 ms 17484 KB Output is correct
26 Correct 22 ms 17472 KB Output is correct
27 Correct 33 ms 18412 KB Output is correct
28 Correct 38 ms 21728 KB Output is correct
29 Correct 42 ms 32964 KB Output is correct
30 Correct 105 ms 36472 KB Output is correct
31 Correct 138 ms 43380 KB Output is correct
32 Correct 171 ms 43332 KB Output is correct
33 Correct 50 ms 43332 KB Output is correct
34 Correct 144 ms 43400 KB Output is correct
35 Correct 143 ms 43332 KB Output is correct
36 Correct 115 ms 43380 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5452 KB Output is correct
2 Correct 5 ms 7124 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 2 ms 4556 KB Output is correct
5 Correct 4 ms 8908 KB Output is correct
6 Correct 13 ms 13248 KB Output is correct
7 Correct 8 ms 14924 KB Output is correct
8 Correct 11 ms 17484 KB Output is correct
9 Correct 10 ms 17484 KB Output is correct
10 Correct 11 ms 17480 KB Output is correct
11 Correct 10 ms 17484 KB Output is correct
12 Correct 10 ms 17488 KB Output is correct
13 Correct 25 ms 17460 KB Output is correct
14 Correct 30 ms 18368 KB Output is correct
15 Correct 30 ms 21736 KB Output is correct
16 Correct 45 ms 33212 KB Output is correct
17 Correct 105 ms 36416 KB Output is correct
18 Correct 176 ms 43452 KB Output is correct
19 Correct 158 ms 43380 KB Output is correct
20 Correct 39 ms 43332 KB Output is correct
21 Correct 158 ms 43332 KB Output is correct
22 Correct 151 ms 43332 KB Output is correct
23 Correct 109 ms 43332 KB Output is correct
24 Correct 150 ms 43740 KB Output is correct
25 Correct 185 ms 55724 KB Output is correct
26 Correct 260 ms 66832 KB Output is correct
27 Correct 432 ms 77988 KB Output is correct
28 Runtime error 822 ms 170460 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5452 KB Output is correct
2 Correct 4 ms 7116 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 3 ms 4556 KB Output is correct
5 Correct 4 ms 8908 KB Output is correct
6 Correct 14 ms 13236 KB Output is correct
7 Correct 9 ms 14924 KB Output is correct
8 Correct 10 ms 17496 KB Output is correct
9 Correct 11 ms 17448 KB Output is correct
10 Correct 10 ms 17408 KB Output is correct
11 Correct 10 ms 17492 KB Output is correct
12 Correct 11 ms 17484 KB Output is correct
13 Correct 29 ms 17584 KB Output is correct
14 Correct 3 ms 5452 KB Output is correct
15 Correct 3 ms 5452 KB Output is correct
16 Correct 3 ms 5456 KB Output is correct
17 Correct 2 ms 4556 KB Output is correct
18 Correct 5 ms 8900 KB Output is correct
19 Correct 13 ms 13252 KB Output is correct
20 Correct 10 ms 14924 KB Output is correct
21 Correct 23 ms 17536 KB Output is correct
22 Correct 16 ms 17428 KB Output is correct
23 Correct 19 ms 17452 KB Output is correct
24 Correct 10 ms 17476 KB Output is correct
25 Correct 14 ms 17476 KB Output is correct
26 Correct 23 ms 17484 KB Output is correct
27 Runtime error 2 ms 460 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5440 KB Output is correct
2 Correct 4 ms 7116 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 2 ms 4556 KB Output is correct
5 Correct 5 ms 8912 KB Output is correct
6 Correct 14 ms 13156 KB Output is correct
7 Correct 11 ms 14924 KB Output is correct
8 Correct 11 ms 17484 KB Output is correct
9 Correct 13 ms 17540 KB Output is correct
10 Correct 11 ms 17472 KB Output is correct
11 Correct 11 ms 17476 KB Output is correct
12 Correct 11 ms 17568 KB Output is correct
13 Correct 25 ms 17548 KB Output is correct
14 Runtime error 2 ms 460 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -