oj.uz

Submission #552604

# Submission time Handle Problem Language Result Execution time Memory
552604 2022-04-23T11:56:58 Z QwertyPi Bali Sculptures (APIO15_sculpture) C++14
71 / 100
 96 ms 95140 KB 
#include <bits/stdc++.h>
#define int long long
#define INF (1LL << 60)
using namespace std;
const int N = 2001;
int dp[N][N], dp2[N];
int s[N], A[N];
vector<int> vals[N][N];
typedef uint32_t uint;
bool valid[N][N];
int n, a, b;
bool check(int mask){
	for(int i = 0; i < n; i++){
		for(int j = i; j < n; j++){
			int v = s[j + 1] - s[i];
			valid[i][j] = (v | mask) == mask;
		}
	}
	if(n > 100){
		fill(dp2 + 1, dp2 + n + 1, INF);
		for(int i = 0; i < n; i++){
			for(int j = 0; j <= i; j++){
				dp2[i + 1] = min(dp2[i + 1], dp2[j] + valid[j][i]);
			}
		}
		return dp2[n] <= b;
	}else{
		for(int i = 0; i <= n; i++){
			for(int j = 0; j <= n; j++){
				dp[i][j] = false;
			}
		}
		dp[0][0] = true;
		for(int tr = 0; tr < n; tr++){
			for(int i = 0; i < n; i++){
				for(int j = i; j < n; j++){
					dp[tr + 1][j + 1] |= dp[tr][i] & valid[i][j];
				}
			}
		}
		bool ans = false;
		for(int i = a; i <= b; i++){
			ans |= dp[i][n];
		}
		return ans;
	}
}

int32_t main(){
	cin >> n >> a >> b;
	vals[0][0].push_back(0);
	for(int i = 1; i <= n; i++) cin >> A[i], s[i] = s[i - 1] + A[i];
	int mask = 0;
	for(int j = 60; j >= 0; j--){
		if(!check(mask + (1LL << j) - 1)){
			mask += 1LL << j;
		}
	}
	cout << mask << endl;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 94348 KB Output is correct
2 Correct 48 ms 94284 KB Output is correct
3 Correct 48 ms 94252 KB Output is correct
4 Correct 59 ms 94352 KB Output is correct
5 Correct 47 ms 94296 KB Output is correct
6 Correct 45 ms 94428 KB Output is correct
7 Correct 50 ms 94396 KB Output is correct
8 Correct 50 ms 94412 KB Output is correct
9 Correct 54 ms 94396 KB Output is correct
10 Correct 47 ms 94392 KB Output is correct
11 Correct 52 ms 94416 KB Output is correct
12 Correct 45 ms 94396 KB Output is correct
13 Correct 45 ms 94356 KB Output is correct
14 Correct 51 ms 94340 KB Output is correct
15 Correct 54 ms 94356 KB Output is correct
16 Correct 46 ms 94372 KB Output is correct
17 Correct 55 ms 94296 KB Output is correct
18 Correct 44 ms 94284 KB Output is correct
19 Correct 44 ms 94400 KB Output is correct
20 Correct 44 ms 94384 KB Output is correct
21 Correct 45 ms 94420 KB Output is correct
22 Correct 45 ms 94412 KB Output is correct
23 Correct 48 ms 94412 KB Output is correct
24 Correct 47 ms 94432 KB Output is correct
25 Correct 46 ms 94380 KB Output is correct
26 Correct 49 ms 94412 KB Output is correct
27 Correct 45 ms 94336 KB Output is correct
28 Correct 46 ms 94320 KB Output is correct
29 Correct 55 ms 94284 KB Output is correct
30 Correct 52 ms 94512 KB Output is correct
31 Correct 46 ms 94368 KB Output is correct
32 Correct 47 ms 94340 KB Output is correct
33 Correct 46 ms 94368 KB Output is correct
34 Correct 57 ms 94372 KB Output is correct
35 Correct 50 ms 94412 KB Output is correct
36 Correct 47 ms 94364 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 94328 KB Output is correct
2 Correct 47 ms 94352 KB Output is correct
3 Correct 46 ms 94296 KB Output is correct
4 Correct 50 ms 94380 KB Output is correct
5 Correct 46 ms 94320 KB Output is correct
6 Correct 46 ms 94368 KB Output is correct
7 Correct 47 ms 94416 KB Output is correct
8 Correct 47 ms 94344 KB Output is correct
9 Correct 49 ms 94400 KB Output is correct
10 Correct 46 ms 94428 KB Output is correct
11 Correct 53 ms 94428 KB Output is correct
12 Correct 47 ms 94444 KB Output is correct
13 Correct 49 ms 94388 KB Output is correct
14 Correct 47 ms 94288 KB Output is correct
15 Correct 45 ms 94264 KB Output is correct
16 Correct 46 ms 94280 KB Output is correct
17 Correct 47 ms 94316 KB Output is correct
18 Correct 45 ms 94348 KB Output is correct
19 Correct 46 ms 94420 KB Output is correct
20 Correct 49 ms 94420 KB Output is correct
21 Correct 46 ms 94440 KB Output is correct
22 Correct 56 ms 94392 KB Output is correct
23 Correct 47 ms 94344 KB Output is correct
24 Correct 47 ms 94412 KB Output is correct
25 Correct 49 ms 94416 KB Output is correct
26 Correct 56 ms 94436 KB Output is correct
27 Correct 45 ms 94452 KB Output is correct
28 Correct 49 ms 94360 KB Output is correct
29 Correct 58 ms 94520 KB Output is correct
30 Correct 48 ms 94556 KB Output is correct
31 Correct 60 ms 94572 KB Output is correct
32 Correct 52 ms 94652 KB Output is correct
33 Correct 51 ms 94616 KB Output is correct
34 Correct 49 ms 94548 KB Output is correct
35 Correct 48 ms 94548 KB Output is correct
36 Correct 54 ms 94644 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 94260 KB Output is correct
2 Correct 45 ms 94292 KB Output is correct
3 Correct 44 ms 94312 KB Output is correct
4 Correct 51 ms 94348 KB Output is correct
5 Correct 51 ms 94292 KB Output is correct
6 Correct 48 ms 94300 KB Output is correct
7 Correct 49 ms 94412 KB Output is correct
8 Correct 53 ms 94412 KB Output is correct
9 Correct 48 ms 94472 KB Output is correct
10 Correct 47 ms 94444 KB Output is correct
11 Correct 53 ms 94384 KB Output is correct
12 Correct 49 ms 94412 KB Output is correct
13 Correct 58 ms 94408 KB Output is correct
14 Correct 49 ms 94452 KB Output is correct
15 Correct 61 ms 94460 KB Output is correct
16 Correct 57 ms 94556 KB Output is correct
17 Correct 59 ms 94536 KB Output is correct
18 Correct 61 ms 94596 KB Output is correct
19 Correct 67 ms 94608 KB Output is correct
20 Correct 54 ms 94580 KB Output is correct
21 Correct 60 ms 94580 KB Output is correct
22 Correct 60 ms 94608 KB Output is correct
23 Correct 65 ms 94540 KB Output is correct
24 Correct 62 ms 94540 KB Output is correct
25 Correct 60 ms 94652 KB Output is correct
26 Correct 65 ms 94848 KB Output is correct
27 Correct 81 ms 95020 KB Output is correct
28 Correct 87 ms 95008 KB Output is correct
29 Correct 77 ms 95008 KB Output is correct
30 Correct 82 ms 95012 KB Output is correct
31 Correct 96 ms 95008 KB Output is correct
32 Correct 73 ms 95008 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 94344 KB Output is correct
2 Correct 52 ms 94284 KB Output is correct
3 Correct 69 ms 94280 KB Output is correct
4 Correct 53 ms 94244 KB Output is correct
5 Correct 61 ms 94280 KB Output is correct
6 Correct 56 ms 94360 KB Output is correct
7 Correct 47 ms 94420 KB Output is correct
8 Correct 53 ms 94348 KB Output is correct
9 Correct 52 ms 94344 KB Output is correct
10 Correct 49 ms 94412 KB Output is correct
11 Correct 54 ms 94404 KB Output is correct
12 Correct 61 ms 94404 KB Output is correct
13 Correct 56 ms 94400 KB Output is correct
14 Correct 53 ms 94444 KB Output is correct
15 Correct 48 ms 94296 KB Output is correct
16 Correct 48 ms 94284 KB Output is correct
17 Correct 58 ms 94356 KB Output is correct
18 Correct 57 ms 94284 KB Output is correct
19 Correct 47 ms 94396 KB Output is correct
20 Correct 49 ms 94392 KB Output is correct
21 Correct 52 ms 94404 KB Output is correct
22 Correct 46 ms 94360 KB Output is correct
23 Correct 50 ms 94420 KB Output is correct
24 Correct 64 ms 94432 KB Output is correct
25 Correct 51 ms 94384 KB Output is correct
26 Correct 54 ms 94352 KB Output is correct
27 Correct 60 ms 94328 KB Output is correct
28 Correct 72 ms 94328 KB Output is correct
29 Correct 62 ms 94356 KB Output is correct
30 Correct 57 ms 94388 KB Output is correct
31 Correct 54 ms 94356 KB Output is correct
32 Correct 51 ms 94404 KB Output is correct
33 Correct 64 ms 94352 KB Output is correct
34 Correct 60 ms 94356 KB Output is correct
35 Correct 49 ms 94380 KB Output is correct
36 Correct 62 ms 94572 KB Output is correct
37 Correct 54 ms 94404 KB Output is correct
38 Correct 49 ms 94412 KB Output is correct
39 Correct 55 ms 94468 KB Output is correct
40 Correct 48 ms 94512 KB Output is correct
41 Correct 60 ms 94548 KB Output is correct
42 Correct 73 ms 94672 KB Output is correct
43 Correct 51 ms 94548 KB Output is correct
44 Correct 52 ms 94588 KB Output is correct
45 Correct 51 ms 94628 KB Output is correct
46 Correct 59 ms 94600 KB Output is correct
47 Correct 56 ms 94612 KB Output is correct
48 Correct 55 ms 94668 KB Output is correct
49 Correct 62 ms 94752 KB Output is correct
50 Correct 84 ms 94836 KB Output is correct
51 Correct 75 ms 95008 KB Output is correct
52 Correct 72 ms 94912 KB Output is correct
53 Correct 76 ms 95012 KB Output is correct
54 Correct 92 ms 95092 KB Output is correct
55 Correct 95 ms 95008 KB Output is correct
56 Correct 54 ms 94620 KB Output is correct
57 Correct 59 ms 94832 KB Output is correct
58 Correct 65 ms 94832 KB Output is correct
59 Correct 87 ms 94968 KB Output is correct
60 Correct 82 ms 95012 KB Output is correct
61 Correct 77 ms 95008 KB Output is correct
62 Correct 79 ms 94924 KB Output is correct
63 Correct 95 ms 95140 KB Output is correct
64 Correct 68 ms 94928 KB Output is correct
65 Correct 53 ms 94632 KB Output is correct
66 Correct 63 ms 94748 KB Output is correct
67 Correct 72 ms 94836 KB Output is correct
68 Correct 70 ms 94940 KB Output is correct
69 Correct 79 ms 94992 KB Output is correct
70 Correct 75 ms 94964 KB Output is correct
71 Correct 88 ms 95016 KB Output is correct
72 Correct 84 ms 94960 KB Output is correct
73 Correct 76 ms 95012 KB Output is correct
74 Correct 77 ms 94972 KB Output is correct

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 94288 KB Output is correct
2 Correct 96 ms 94316 KB Output is correct
3 Correct 65 ms 94248 KB Output is correct
4 Correct 53 ms 94268 KB Output is correct
5 Correct 59 ms 94364 KB Output is correct
6 Correct 69 ms 94320 KB Output is correct
7 Correct 53 ms 94412 KB Output is correct
8 Correct 53 ms 94372 KB Output is correct
9 Correct 75 ms 94368 KB Output is correct
10 Correct 58 ms 94452 KB Output is correct
11 Correct 60 ms 94416 KB Output is correct
12 Correct 62 ms 94376 KB Output is correct
13 Correct 51 ms 94408 KB Output is correct
14 Correct 53 ms 94292 KB Output is correct
15 Correct 60 ms 94284 KB Output is correct
16 Correct 62 ms 94400 KB Output is correct
17 Correct 61 ms 94484 KB Output is correct
18 Correct 63 ms 94396 KB Output is correct
19 Correct 54 ms 94440 KB Output is correct
20 Correct 63 ms 94416 KB Output is correct
21 Correct 53 ms 94400 KB Output is correct
22 Correct 59 ms 94332 KB Output is correct
23 Correct 53 ms 94412 KB Output is correct
24 Correct 56 ms 94456 KB Output is correct
25 Correct 55 ms 94432 KB Output is correct
26 Correct 52 ms 94516 KB Output is correct
27 Correct 52 ms 94552 KB Output is correct
28 Correct 57 ms 94632 KB Output is correct
29 Correct 65 ms 94588 KB Output is correct
30 Correct 58 ms 94672 KB Output is correct
31 Correct 55 ms 94592 KB Output is correct
32 Correct 54 ms 94644 KB Output is correct
33 Correct 54 ms 94532 KB Output is correct
34 Correct 54 ms 94540 KB Output is correct
35 Correct 58 ms 94652 KB Output is correct
36 Correct 66 ms 94764 KB Output is correct
37 Correct 68 ms 95052 KB Output is correct
38 Correct 75 ms 94964 KB Output is correct
39 Correct 80 ms 94964 KB Output is correct
40 Correct 77 ms 94908 KB Output is correct
41 Correct 74 ms 95008 KB Output is correct
42 Correct 76 ms 94924 KB Output is correct
43 Correct 58 ms 94540 KB Output is correct
44 Correct 70 ms 94772 KB Output is correct
45 Correct 74 ms 94944 KB Output is correct
46 Correct 73 ms 95008 KB Output is correct
47 Correct 75 ms 94924 KB Output is correct
48 Correct 76 ms 94952 KB Output is correct
49 Correct 75 ms 94964 KB Output is correct
50 Correct 76 ms 94952 KB Output is correct
51 Incorrect 51 ms 94468 KB Output isn't correct
52 Halted 0 ms 0 KB -