oj.uz

Submission #527576

# Submission time Handle Problem Language Result Execution time Memory
527576 2022-02-17T17:08:06 Z SlavicG Bali Sculptures (APIO15_sculpture) C++17
37 / 100
 766 ms 90188 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 = 105, 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 5708 KB Output is correct
2 Correct 4 ms 7500 KB Output is correct
3 Correct 1 ms 1228 KB Output is correct
4 Correct 2 ms 4812 KB Output is correct
5 Correct 4 ms 9292 KB Output is correct
6 Correct 16 ms 13992 KB Output is correct
7 Correct 9 ms 15564 KB Output is correct
8 Correct 11 ms 18316 KB Output is correct
9 Correct 11 ms 18380 KB Output is correct
10 Correct 10 ms 18124 KB Output is correct
11 Correct 11 ms 18116 KB Output is correct
12 Correct 11 ms 18380 KB Output is correct
13 Correct 24 ms 18380 KB Output is correct
14 Correct 3 ms 5708 KB Output is correct
15 Correct 3 ms 5708 KB Output is correct
16 Correct 3 ms 5708 KB Output is correct
17 Correct 2 ms 4812 KB Output is correct
18 Correct 7 ms 9292 KB Output is correct
19 Correct 14 ms 13772 KB Output is correct
20 Correct 8 ms 15692 KB Output is correct
21 Correct 15 ms 18380 KB Output is correct
22 Correct 15 ms 18168 KB Output is correct
23 Correct 19 ms 18156 KB Output is correct
24 Correct 10 ms 18064 KB Output is correct
25 Correct 15 ms 18340 KB Output is correct
26 Correct 22 ms 18440 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 4 ms 5708 KB Output is correct
2 Correct 4 ms 7492 KB Output is correct
3 Correct 1 ms 1228 KB Output is correct
4 Correct 2 ms 4812 KB Output is correct
5 Correct 5 ms 9280 KB Output is correct
6 Correct 13 ms 13848 KB Output is correct
7 Correct 8 ms 15616 KB Output is correct
8 Correct 10 ms 18380 KB Output is correct
9 Correct 12 ms 18380 KB Output is correct
10 Correct 11 ms 18124 KB Output is correct
11 Correct 10 ms 18132 KB Output is correct
12 Correct 11 ms 18396 KB Output is correct
13 Correct 35 ms 18300 KB Output is correct
14 Correct 3 ms 5708 KB Output is correct
15 Correct 3 ms 5708 KB Output is correct
16 Correct 3 ms 5708 KB Output is correct
17 Correct 3 ms 4812 KB Output is correct
18 Correct 5 ms 9292 KB Output is correct
19 Correct 13 ms 13812 KB Output is correct
20 Correct 8 ms 15692 KB Output is correct
21 Correct 14 ms 18300 KB Output is correct
22 Correct 14 ms 18244 KB Output is correct
23 Correct 14 ms 18052 KB Output is correct
24 Correct 10 ms 18124 KB Output is correct
25 Correct 15 ms 18380 KB Output is correct
26 Correct 24 ms 18328 KB Output is correct
27 Correct 32 ms 19308 KB Output is correct
28 Correct 40 ms 22848 KB Output is correct
29 Correct 60 ms 34648 KB Output is correct
30 Correct 110 ms 38268 KB Output is correct
31 Correct 141 ms 45540 KB Output is correct
32 Correct 142 ms 45268 KB Output is correct
33 Correct 50 ms 45292 KB Output is correct
34 Correct 155 ms 45468 KB Output is correct
35 Correct 157 ms 45464 KB Output is correct
36 Correct 124 ms 45604 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5708 KB Output is correct
2 Correct 3 ms 7500 KB Output is correct
3 Correct 1 ms 1228 KB Output is correct
4 Correct 3 ms 4812 KB Output is correct
5 Correct 5 ms 9292 KB Output is correct
6 Correct 20 ms 13836 KB Output is correct
7 Correct 9 ms 15576 KB Output is correct
8 Correct 12 ms 18320 KB Output is correct
9 Correct 10 ms 18288 KB Output is correct
10 Correct 11 ms 18064 KB Output is correct
11 Correct 10 ms 18116 KB Output is correct
12 Correct 11 ms 18380 KB Output is correct
13 Correct 25 ms 18344 KB Output is correct
14 Correct 33 ms 19272 KB Output is correct
15 Correct 29 ms 22884 KB Output is correct
16 Correct 42 ms 34668 KB Output is correct
17 Correct 109 ms 38216 KB Output is correct
18 Correct 150 ms 45572 KB Output is correct
19 Correct 145 ms 45288 KB Output is correct
20 Correct 40 ms 45224 KB Output is correct
21 Correct 147 ms 45564 KB Output is correct
22 Correct 156 ms 45444 KB Output is correct
23 Correct 114 ms 45508 KB Output is correct
24 Correct 154 ms 45724 KB Output is correct
25 Correct 204 ms 58196 KB Output is correct
26 Correct 363 ms 70060 KB Output is correct
27 Correct 440 ms 81684 KB Output is correct
28 Correct 766 ms 90188 KB Output is correct
29 Correct 746 ms 88900 KB Output is correct
30 Correct 134 ms 88660 KB Output is correct
31 Correct 506 ms 89616 KB Output is correct
32 Correct 632 ms 89520 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5708 KB Output is correct
2 Correct 4 ms 7500 KB Output is correct
3 Correct 1 ms 1220 KB Output is correct
4 Correct 2 ms 4812 KB Output is correct
5 Correct 4 ms 9292 KB Output is correct
6 Correct 15 ms 13884 KB Output is correct
7 Correct 9 ms 15564 KB Output is correct
8 Correct 11 ms 18364 KB Output is correct
9 Correct 12 ms 18340 KB Output is correct
10 Correct 11 ms 18096 KB Output is correct
11 Correct 10 ms 18124 KB Output is correct
12 Correct 12 ms 18380 KB Output is correct
13 Correct 25 ms 18368 KB Output is correct
14 Correct 3 ms 5708 KB Output is correct
15 Correct 3 ms 5708 KB Output is correct
16 Correct 4 ms 5716 KB Output is correct
17 Correct 2 ms 4812 KB Output is correct
18 Correct 5 ms 9292 KB Output is correct
19 Correct 14 ms 13804 KB Output is correct
20 Correct 8 ms 15656 KB Output is correct
21 Correct 14 ms 18380 KB Output is correct
22 Correct 15 ms 18252 KB Output is correct
23 Correct 15 ms 18124 KB Output is correct
24 Correct 11 ms 18064 KB Output is correct
25 Correct 17 ms 18388 KB Output is correct
26 Correct 23 ms 18380 KB Output is correct
27 Runtime error 2 ms 392 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 5708 KB Output is correct
2 Correct 4 ms 7500 KB Output is correct
3 Correct 1 ms 1228 KB Output is correct
4 Correct 2 ms 4812 KB Output is correct
5 Correct 4 ms 9292 KB Output is correct
6 Correct 19 ms 13904 KB Output is correct
7 Correct 9 ms 15560 KB Output is correct
8 Correct 11 ms 18380 KB Output is correct
9 Correct 13 ms 18296 KB Output is correct
10 Correct 12 ms 18124 KB Output is correct
11 Correct 10 ms 18128 KB Output is correct
12 Correct 13 ms 18380 KB Output is correct
13 Correct 25 ms 18372 KB Output is correct
14 Runtime error 3 ms 400 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -