Submission #401375

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
401375	2021-05-10T03:51:49 Z	Azimjon	Bali Sculptures (APIO15_sculpture)	C++17	25 / 100	1000 ms	35312 KB

sculpture

// Muallif: Azimjon Mehmonali o'g'li

#include <bits/stdc++.h>

using namespace std;

#define int long long

const long double PI = 3.1415926535897;
const int mod = 1000000007LL;
const int INF = (1ll << 35) - 1;
const int N = 2111;
const int K = 2111;

int n, k, a, b;
int y[N], p[N], dp[K][N], pp[K][N];

bool check(int mask, int cand) {
	for (int i = 0; i < 60; i++) {
		if (!(mask & (1ll << i)) && (cand & (1ll << i))) return false;
	}

	return true;
}

bool can(int mask) {
	memset(dp, 0, sizeof(dp));
	for (int i = 1; i <= n; i++)
		dp[0][i] = check(mask, p[i]);

	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j < i; j++) {
				dp[k][i] |= dp[k - 1][j] && check(mask, p[i] - p[j]);
			}
		}
	}
	bool fl = 0;
	for (int i = a; i <= b; i++) {
		fl |= dp[i - 1][n];
	}

	return fl;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> a >> b;

	for (int i = 1; i <= n; i++) {
		cin >> y[i];

		p[i] = p[i - 1] + y[i];
	}

	int nt = (1ll << 61) - 1;

	for (int i = 60; i >= 0; i--) {
		if (can(nt - (1ll << i))) {
			nt -= (1ll << i);
		}
	}

	cout << nt << endl;

	return 0;
}

Subtask #1

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	289 ms	35268 KB	Output is correct
2	Correct	288 ms	35204 KB	Output is correct
3	Correct	283 ms	35192 KB	Output is correct
4	Correct	293 ms	35208 KB	Output is correct
5	Correct	289 ms	35188 KB	Output is correct
6	Correct	296 ms	35188 KB	Output is correct
7	Correct	294 ms	35192 KB	Output is correct
8	Correct	296 ms	35192 KB	Output is correct
9	Correct	295 ms	35200 KB	Output is correct
10	Correct	310 ms	35204 KB	Output is correct
11	Correct	293 ms	35192 KB	Output is correct
12	Correct	298 ms	35272 KB	Output is correct
13	Correct	293 ms	35188 KB	Output is correct
14	Correct	305 ms	35192 KB	Output is correct
15	Correct	286 ms	35148 KB	Output is correct
16	Correct	289 ms	35200 KB	Output is correct
17	Correct	290 ms	35148 KB	Output is correct
18	Correct	296 ms	35188 KB	Output is correct
19	Correct	293 ms	35192 KB	Output is correct
20	Correct	291 ms	35208 KB	Output is correct
21	Correct	297 ms	35268 KB	Output is correct
22	Correct	305 ms	35152 KB	Output is correct
23	Correct	303 ms	35196 KB	Output is correct
24	Correct	308 ms	35204 KB	Output is correct
25	Correct	307 ms	35148 KB	Output is correct
26	Correct	304 ms	35148 KB	Output is correct
27	Correct	296 ms	35148 KB	Output is correct
28	Correct	304 ms	35148 KB	Output is correct
29	Correct	305 ms	35148 KB	Output is correct
30	Correct	304 ms	35192 KB	Output is correct
31	Correct	300 ms	35192 KB	Output is correct
32	Correct	304 ms	35192 KB	Output is correct
33	Correct	296 ms	35192 KB	Output is correct
34	Correct	299 ms	35192 KB	Output is correct
35	Correct	303 ms	35240 KB	Output is correct
36	Correct	306 ms	35204 KB	Output is correct

Subtask #2

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	285 ms	35184 KB	Output is correct
2	Correct	287 ms	35196 KB	Output is correct
3	Correct	282 ms	35148 KB	Output is correct
4	Correct	283 ms	35192 KB	Output is correct
5	Correct	289 ms	35188 KB	Output is correct
6	Correct	290 ms	35204 KB	Output is correct
7	Correct	298 ms	35196 KB	Output is correct
8	Correct	315 ms	35100 KB	Output is correct
9	Correct	298 ms	35268 KB	Output is correct
10	Correct	295 ms	35124 KB	Output is correct
11	Correct	293 ms	35208 KB	Output is correct
12	Correct	298 ms	35196 KB	Output is correct
13	Correct	301 ms	35140 KB	Output is correct
14	Correct	284 ms	35200 KB	Output is correct
15	Correct	287 ms	35148 KB	Output is correct
16	Correct	284 ms	35204 KB	Output is correct
17	Correct	293 ms	35148 KB	Output is correct
18	Correct	296 ms	35192 KB	Output is correct
19	Correct	297 ms	35196 KB	Output is correct
20	Correct	302 ms	35200 KB	Output is correct
21	Correct	297 ms	35192 KB	Output is correct
22	Correct	304 ms	35192 KB	Output is correct
23	Correct	296 ms	35148 KB	Output is correct
24	Correct	295 ms	35312 KB	Output is correct
25	Correct	296 ms	35148 KB	Output is correct
26	Correct	293 ms	35204 KB	Output is correct
27	Correct	301 ms	35192 KB	Output is correct
28	Correct	303 ms	35100 KB	Output is correct
29	Correct	335 ms	35192 KB	Output is correct
30	Correct	354 ms	35208 KB	Output is correct
31	Correct	389 ms	35148 KB	Output is correct
32	Correct	386 ms	35200 KB	Output is correct
33	Correct	393 ms	35148 KB	Output is correct
34	Correct	389 ms	35196 KB	Output is correct
35	Correct	390 ms	35148 KB	Output is correct
36	Correct	403 ms	35196 KB	Output is correct

Subtask #3

0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	292 ms	35184 KB	Output is correct
2	Correct	301 ms	35164 KB	Output is correct
3	Correct	290 ms	35228 KB	Output is correct
4	Correct	286 ms	35200 KB	Output is correct
5	Correct	286 ms	35268 KB	Output is correct
6	Correct	292 ms	35192 KB	Output is correct
7	Correct	290 ms	35148 KB	Output is correct
8	Correct	297 ms	35188 KB	Output is correct
9	Correct	294 ms	35148 KB	Output is correct
10	Correct	293 ms	35208 KB	Output is correct
11	Correct	293 ms	35148 KB	Output is correct
12	Correct	303 ms	35080 KB	Output is correct
13	Correct	292 ms	35192 KB	Output is correct
14	Correct	301 ms	35192 KB	Output is correct
15	Correct	298 ms	35148 KB	Output is correct
16	Correct	339 ms	35192 KB	Output is correct
17	Correct	356 ms	35196 KB	Output is correct
18	Correct	391 ms	35116 KB	Output is correct
19	Correct	396 ms	35268 KB	Output is correct
20	Correct	396 ms	35256 KB	Output is correct
21	Correct	397 ms	35208 KB	Output is correct
22	Correct	399 ms	35192 KB	Output is correct
23	Correct	393 ms	35268 KB	Output is correct
24	Correct	405 ms	35148 KB	Output is correct
25	Correct	511 ms	35268 KB	Output is correct
26	Correct	679 ms	35148 KB	Output is correct
27	Correct	898 ms	35268 KB	Output is correct
28	Execution timed out	1070 ms	35148 KB	Time limit exceeded
29	Halted	0 ms	0 KB	-

Subtask #4

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	280 ms	35184 KB	Output is correct
2	Correct	292 ms	35196 KB	Output is correct
3	Correct	285 ms	35192 KB	Output is correct
4	Correct	288 ms	35192 KB	Output is correct
5	Correct	282 ms	35192 KB	Output is correct
6	Correct	287 ms	35240 KB	Output is correct
7	Correct	290 ms	35188 KB	Output is correct
8	Correct	298 ms	35148 KB	Output is correct
9	Correct	288 ms	35192 KB	Output is correct
10	Correct	291 ms	35192 KB	Output is correct
11	Correct	296 ms	35148 KB	Output is correct
12	Correct	293 ms	35196 KB	Output is correct
13	Correct	293 ms	35192 KB	Output is correct
14	Correct	292 ms	35192 KB	Output is correct
15	Correct	287 ms	35232 KB	Output is correct
16	Correct	302 ms	35100 KB	Output is correct
17	Correct	289 ms	35204 KB	Output is correct
18	Correct	283 ms	35256 KB	Output is correct
19	Correct	283 ms	35268 KB	Output is correct
20	Correct	295 ms	35292 KB	Output is correct
21	Correct	291 ms	35148 KB	Output is correct
22	Correct	296 ms	35188 KB	Output is correct
23	Correct	297 ms	35140 KB	Output is correct
24	Correct	293 ms	35192 KB	Output is correct
25	Correct	292 ms	35148 KB	Output is correct
26	Correct	294 ms	35192 KB	Output is correct
27	Correct	293 ms	35148 KB	Output is correct
28	Correct	294 ms	35148 KB	Output is correct
29	Correct	287 ms	35188 KB	Output is correct
30	Correct	292 ms	35268 KB	Output is correct
31	Correct	292 ms	35196 KB	Output is correct
32	Correct	296 ms	35188 KB	Output is correct
33	Correct	294 ms	35148 KB	Output is correct
34	Correct	304 ms	35252 KB	Output is correct
35	Correct	291 ms	35148 KB	Output is correct
36	Correct	292 ms	35156 KB	Output is correct
37	Correct	296 ms	35148 KB	Output is correct
38	Correct	302 ms	35140 KB	Output is correct
39	Correct	333 ms	35196 KB	Output is correct
40	Correct	348 ms	35176 KB	Output is correct
41	Correct	385 ms	35268 KB	Output is correct
42	Correct	392 ms	35192 KB	Output is correct
43	Correct	387 ms	35148 KB	Output is correct
44	Correct	389 ms	35148 KB	Output is correct
45	Correct	393 ms	35192 KB	Output is correct
46	Correct	394 ms	35200 KB	Output is correct
47	Correct	396 ms	35268 KB	Output is correct
48	Correct	514 ms	35268 KB	Output is correct
49	Correct	673 ms	35188 KB	Output is correct
50	Correct	907 ms	35268 KB	Output is correct
51	Execution timed out	1084 ms	35148 KB	Time limit exceeded
52	Halted	0 ms	0 KB	-

Subtask #5

0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	287 ms	35148 KB	Output is correct
2	Correct	290 ms	35184 KB	Output is correct
3	Correct	290 ms	35204 KB	Output is correct
4	Correct	288 ms	35148 KB	Output is correct
5	Correct	292 ms	35148 KB	Output is correct
6	Correct	297 ms	35148 KB	Output is correct
7	Correct	302 ms	35200 KB	Output is correct
8	Correct	297 ms	35280 KB	Output is correct
9	Correct	297 ms	35148 KB	Output is correct
10	Correct	293 ms	35192 KB	Output is correct
11	Correct	287 ms	35192 KB	Output is correct
12	Correct	298 ms	35148 KB	Output is correct
13	Correct	289 ms	35176 KB	Output is correct
14	Correct	286 ms	35268 KB	Output is correct
15	Correct	288 ms	35192 KB	Output is correct
16	Correct	292 ms	35312 KB	Output is correct
17	Correct	291 ms	35212 KB	Output is correct
18	Correct	292 ms	35204 KB	Output is correct
19	Correct	289 ms	35268 KB	Output is correct
20	Correct	300 ms	35192 KB	Output is correct
21	Correct	289 ms	35276 KB	Output is correct
22	Correct	297 ms	35208 KB	Output is correct
23	Correct	291 ms	35148 KB	Output is correct
24	Correct	297 ms	35124 KB	Output is correct
25	Correct	301 ms	35192 KB	Output is correct
26	Correct	332 ms	35192 KB	Output is correct
27	Correct	353 ms	35260 KB	Output is correct
28	Correct	390 ms	35160 KB	Output is correct
29	Correct	387 ms	35268 KB	Output is correct
30	Correct	393 ms	35208 KB	Output is correct
31	Correct	390 ms	35196 KB	Output is correct
32	Correct	397 ms	35196 KB	Output is correct
33	Correct	399 ms	35224 KB	Output is correct
34	Correct	405 ms	35196 KB	Output is correct
35	Correct	508 ms	35260 KB	Output is correct
36	Correct	677 ms	35192 KB	Output is correct
37	Correct	914 ms	35208 KB	Output is correct
38	Execution timed out	1081 ms	35148 KB	Time limit exceeded
39	Halted	0 ms	0 KB	-