답안 #99472 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
99472	2019-03-04T09:43:58 Z	Shafin666	Bali Sculptures (APIO15_sculpture)	C++14	71 / 100	1000 ms	32068 KB

sculpture

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
typedef long long ll;
typedef long double ld;
using namespace std;

int n, a, b;
ll num[2005], pre[2050];
ll dp[2005], dp2[2005][2005];
ll bit = 43, mask;

ll c(int i, int j) {
	return pre[j] - pre[i-1];
}

void can(int x) {
	mask ^= (1LL << x);

	for(int i = 1; i <= n; i++) {
		dp[i] = 1e18+7;

		for(int j = 0; j < i; j++) {
			if((mask | c(j+1, i)) == mask) dp[i] = min(dp[i], dp[j]+1);
		}
	}
	if(dp[n] > b) mask |= (1LL << x);
}

void can2(int x) {
	mask ^= (1LL << x);

	memset(dp2, 0, sizeof dp2);
	dp2[0][0] = 1;

	for(int k = 1; k <= n; k++) {
		for(int i = 1;  i <= n; i++) {
			for(int j = 0; j < i; j++) {
				if((mask | c(j+1, i)) == mask) dp2[k][i] |= dp2[k-1][j];
			}
		}
	}

	for(int i = a; i <= b; i++) if(dp2[i][n]) return;
	mask |= (1LL << x);
}

int main() 
{
	cin >> n >> a >> b;

	ll mn = 1e18+7;

	for(int i = 1; i <= n; i++) cin >> num[i];
	for(int i = 1; i <= n; i++) pre[i] = pre[i-1] + num[i];

	for(int i = 0; i <= bit; i++) mask |= (1LL << i);

	for(int i = bit; i >= 0; i--) can2(i);

	cout << mask << endl;

	return 0;
}

Compilation message

sculpture.cpp: In function 'int main()':
sculpture.cpp:53:5: warning: unused variable 'mn' [-Wunused-variable]
  ll mn = 1e18+7;
     ^~

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	365 ms	31864 KB	Output is correct
2	Correct	386 ms	31864 KB	Output is correct
3	Correct	389 ms	31992 KB	Output is correct
4	Correct	401 ms	31864 KB	Output is correct
5	Correct	384 ms	31872 KB	Output is correct
6	Correct	352 ms	31868 KB	Output is correct
7	Correct	402 ms	31868 KB	Output is correct
8	Correct	329 ms	31992 KB	Output is correct
9	Correct	332 ms	31964 KB	Output is correct
10	Correct	315 ms	31864 KB	Output is correct
11	Correct	395 ms	31864 KB	Output is correct
12	Correct	303 ms	31872 KB	Output is correct
13	Correct	315 ms	31872 KB	Output is correct
14	Correct	315 ms	31744 KB	Output is correct
15	Correct	384 ms	31864 KB	Output is correct
16	Correct	320 ms	31864 KB	Output is correct
17	Correct	319 ms	31864 KB	Output is correct
18	Correct	356 ms	31996 KB	Output is correct
19	Correct	332 ms	31864 KB	Output is correct
20	Correct	317 ms	31864 KB	Output is correct
21	Correct	300 ms	31864 KB	Output is correct
22	Correct	332 ms	31868 KB	Output is correct
23	Correct	317 ms	31996 KB	Output is correct
24	Correct	404 ms	31872 KB	Output is correct
25	Correct	312 ms	31964 KB	Output is correct
26	Correct	309 ms	31744 KB	Output is correct
27	Correct	307 ms	31872 KB	Output is correct
28	Correct	321 ms	31836 KB	Output is correct
29	Correct	297 ms	31864 KB	Output is correct
30	Correct	308 ms	31864 KB	Output is correct
31	Correct	324 ms	31864 KB	Output is correct
32	Correct	370 ms	31864 KB	Output is correct
33	Correct	365 ms	31744 KB	Output is correct
34	Correct	371 ms	31744 KB	Output is correct
35	Correct	397 ms	31864 KB	Output is correct
36	Correct	397 ms	31864 KB	Output is correct

Subtask #2
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	374 ms	31868 KB	Output is correct
2	Correct	311 ms	31864 KB	Output is correct
3	Correct	326 ms	31740 KB	Output is correct
4	Correct	319 ms	31864 KB	Output is correct
5	Correct	330 ms	31864 KB	Output is correct
6	Correct	320 ms	31992 KB	Output is correct
7	Correct	373 ms	31864 KB	Output is correct
8	Correct	350 ms	31964 KB	Output is correct
9	Correct	344 ms	31872 KB	Output is correct
10	Correct	324 ms	31736 KB	Output is correct
11	Correct	330 ms	31740 KB	Output is correct
12	Correct	327 ms	31864 KB	Output is correct
13	Correct	338 ms	31864 KB	Output is correct
14	Correct	335 ms	31864 KB	Output is correct
15	Correct	324 ms	31864 KB	Output is correct
16	Correct	325 ms	31992 KB	Output is correct
17	Correct	342 ms	31740 KB	Output is correct
18	Correct	319 ms	31836 KB	Output is correct
19	Correct	318 ms	31736 KB	Output is correct
20	Correct	335 ms	31864 KB	Output is correct
21	Correct	335 ms	31872 KB	Output is correct
22	Correct	335 ms	31868 KB	Output is correct
23	Correct	325 ms	31872 KB	Output is correct
24	Correct	322 ms	31872 KB	Output is correct
25	Correct	320 ms	31992 KB	Output is correct
26	Correct	319 ms	31872 KB	Output is correct
27	Correct	307 ms	31832 KB	Output is correct
28	Correct	330 ms	31836 KB	Output is correct
29	Correct	318 ms	31744 KB	Output is correct
30	Correct	323 ms	31836 KB	Output is correct
31	Correct	327 ms	31864 KB	Output is correct
32	Correct	331 ms	31968 KB	Output is correct
33	Correct	407 ms	31992 KB	Output is correct
34	Correct	390 ms	31992 KB	Output is correct
35	Correct	366 ms	31864 KB	Output is correct
36	Correct	334 ms	31964 KB	Output is correct

Subtask #3
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	311 ms	31840 KB	Output is correct
2	Correct	325 ms	31992 KB	Output is correct
3	Correct	329 ms	31872 KB	Output is correct
4	Correct	331 ms	31864 KB	Output is correct
5	Correct	315 ms	31864 KB	Output is correct
6	Correct	318 ms	31864 KB	Output is correct
7	Correct	330 ms	31872 KB	Output is correct
8	Correct	321 ms	31868 KB	Output is correct
9	Correct	362 ms	31872 KB	Output is correct
10	Correct	323 ms	31872 KB	Output is correct
11	Correct	341 ms	31952 KB	Output is correct
12	Correct	321 ms	31864 KB	Output is correct
13	Correct	325 ms	31964 KB	Output is correct
14	Correct	327 ms	31872 KB	Output is correct
15	Correct	412 ms	31964 KB	Output is correct
16	Correct	410 ms	31864 KB	Output is correct
17	Correct	314 ms	31872 KB	Output is correct
18	Correct	333 ms	31744 KB	Output is correct
19	Correct	343 ms	31744 KB	Output is correct
20	Correct	411 ms	31864 KB	Output is correct
21	Correct	354 ms	31864 KB	Output is correct
22	Correct	373 ms	31912 KB	Output is correct
23	Correct	391 ms	31864 KB	Output is correct
24	Correct	345 ms	31836 KB	Output is correct
25	Correct	332 ms	31872 KB	Output is correct
26	Correct	355 ms	31864 KB	Output is correct
27	Correct	413 ms	31864 KB	Output is correct
28	Correct	434 ms	31992 KB	Output is correct
29	Correct	448 ms	31900 KB	Output is correct
30	Correct	412 ms	31872 KB	Output is correct
31	Correct	407 ms	31964 KB	Output is correct
32	Correct	377 ms	31992 KB	Output is correct

Subtask #4
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	317 ms	31836 KB	Output is correct
2	Correct	314 ms	31864 KB	Output is correct
3	Correct	314 ms	31736 KB	Output is correct
4	Correct	311 ms	31836 KB	Output is correct
5	Correct	387 ms	31872 KB	Output is correct
6	Correct	352 ms	31980 KB	Output is correct
7	Correct	322 ms	31964 KB	Output is correct
8	Correct	321 ms	31864 KB	Output is correct
9	Correct	377 ms	31836 KB	Output is correct
10	Correct	312 ms	31864 KB	Output is correct
11	Correct	389 ms	31864 KB	Output is correct
12	Correct	360 ms	31872 KB	Output is correct
13	Correct	316 ms	31864 KB	Output is correct
14	Correct	316 ms	31744 KB	Output is correct
15	Correct	310 ms	31864 KB	Output is correct
16	Correct	313 ms	31872 KB	Output is correct
17	Correct	325 ms	31864 KB	Output is correct
18	Correct	312 ms	31864 KB	Output is correct
19	Correct	307 ms	31864 KB	Output is correct
20	Correct	342 ms	31992 KB	Output is correct
21	Correct	316 ms	31864 KB	Output is correct
22	Correct	313 ms	31872 KB	Output is correct
23	Correct	311 ms	31868 KB	Output is correct
24	Correct	336 ms	31864 KB	Output is correct
25	Correct	327 ms	31864 KB	Output is correct
26	Correct	330 ms	31952 KB	Output is correct
27	Correct	437 ms	31864 KB	Output is correct
28	Correct	483 ms	31864 KB	Output is correct
29	Correct	401 ms	31992 KB	Output is correct
30	Correct	329 ms	31856 KB	Output is correct
31	Correct	319 ms	31864 KB	Output is correct
32	Correct	321 ms	31960 KB	Output is correct
33	Correct	319 ms	31744 KB	Output is correct
34	Correct	371 ms	31864 KB	Output is correct
35	Correct	379 ms	31908 KB	Output is correct
36	Correct	315 ms	31864 KB	Output is correct
37	Correct	325 ms	31872 KB	Output is correct
38	Correct	333 ms	31992 KB	Output is correct
39	Correct	409 ms	31960 KB	Output is correct
40	Correct	367 ms	31864 KB	Output is correct
41	Correct	328 ms	31864 KB	Output is correct
42	Correct	343 ms	31992 KB	Output is correct
43	Correct	331 ms	31864 KB	Output is correct
44	Correct	318 ms	31872 KB	Output is correct
45	Correct	330 ms	31872 KB	Output is correct
46	Correct	323 ms	31864 KB	Output is correct
47	Correct	325 ms	31992 KB	Output is correct
48	Correct	332 ms	31868 KB	Output is correct
49	Correct	330 ms	32000 KB	Output is correct
50	Correct	375 ms	31864 KB	Output is correct
51	Correct	395 ms	31872 KB	Output is correct
52	Correct	418 ms	31916 KB	Output is correct
53	Correct	437 ms	31992 KB	Output is correct
54	Correct	368 ms	31864 KB	Output is correct
55	Correct	358 ms	31868 KB	Output is correct
56	Correct	346 ms	31872 KB	Output is correct
57	Correct	382 ms	31992 KB	Output is correct
58	Correct	346 ms	31832 KB	Output is correct
59	Correct	352 ms	31992 KB	Output is correct
60	Correct	345 ms	31736 KB	Output is correct
61	Correct	356 ms	31872 KB	Output is correct
62	Correct	356 ms	31872 KB	Output is correct
63	Correct	361 ms	31872 KB	Output is correct
64	Correct	356 ms	31992 KB	Output is correct
65	Correct	313 ms	31864 KB	Output is correct
66	Correct	388 ms	31908 KB	Output is correct
67	Correct	393 ms	31992 KB	Output is correct
68	Correct	405 ms	31992 KB	Output is correct
69	Correct	424 ms	31744 KB	Output is correct
70	Correct	423 ms	31840 KB	Output is correct
71	Correct	444 ms	31992 KB	Output is correct
72	Correct	361 ms	31736 KB	Output is correct
73	Correct	416 ms	31864 KB	Output is correct
74	Correct	406 ms	31872 KB	Output is correct

Subtask #5
0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	377 ms	31864 KB	Output is correct
2	Correct	375 ms	31864 KB	Output is correct
3	Correct	330 ms	31868 KB	Output is correct
4	Correct	320 ms	31880 KB	Output is correct
5	Correct	409 ms	31864 KB	Output is correct
6	Correct	399 ms	31928 KB	Output is correct
7	Correct	423 ms	31836 KB	Output is correct
8	Correct	320 ms	31864 KB	Output is correct
9	Correct	356 ms	31864 KB	Output is correct
10	Correct	326 ms	31864 KB	Output is correct
11	Correct	363 ms	31736 KB	Output is correct
12	Correct	423 ms	31968 KB	Output is correct
13	Correct	322 ms	31836 KB	Output is correct
14	Correct	362 ms	31872 KB	Output is correct
15	Correct	399 ms	31836 KB	Output is correct
16	Correct	402 ms	31868 KB	Output is correct
17	Correct	379 ms	31736 KB	Output is correct
18	Correct	398 ms	31864 KB	Output is correct
19	Correct	403 ms	31736 KB	Output is correct
20	Correct	387 ms	31964 KB	Output is correct
21	Correct	385 ms	31736 KB	Output is correct
22	Correct	350 ms	31864 KB	Output is correct
23	Correct	340 ms	31872 KB	Output is correct
24	Correct	316 ms	31964 KB	Output is correct
25	Correct	324 ms	31836 KB	Output is correct
26	Correct	327 ms	31864 KB	Output is correct
27	Correct	314 ms	31736 KB	Output is correct
28	Correct	328 ms	31864 KB	Output is correct
29	Correct	316 ms	31864 KB	Output is correct
30	Correct	319 ms	31864 KB	Output is correct
31	Correct	348 ms	31864 KB	Output is correct
32	Correct	321 ms	31836 KB	Output is correct
33	Correct	310 ms	31744 KB	Output is correct
34	Correct	314 ms	31744 KB	Output is correct
35	Correct	333 ms	31736 KB	Output is correct
36	Correct	359 ms	31736 KB	Output is correct
37	Correct	388 ms	31916 KB	Output is correct
38	Correct	362 ms	31736 KB	Output is correct
39	Correct	394 ms	31868 KB	Output is correct
40	Correct	474 ms	31736 KB	Output is correct
41	Correct	409 ms	31864 KB	Output is correct
42	Correct	370 ms	31744 KB	Output is correct
43	Correct	322 ms	31864 KB	Output is correct
44	Correct	341 ms	31864 KB	Output is correct
45	Correct	409 ms	31992 KB	Output is correct
46	Correct	364 ms	31872 KB	Output is correct
47	Correct	361 ms	32068 KB	Output is correct
48	Correct	350 ms	31864 KB	Output is correct
49	Correct	359 ms	31864 KB	Output is correct
50	Correct	448 ms	31864 KB	Output is correct
51	Correct	352 ms	31888 KB	Output is correct
52	Execution timed out	1079 ms	31872 KB	Time limit exceeded
53	Halted	0 ms	0 KB	-

답안 #99472

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 16.0 / 16.0

Subtask #3 21.0 / 21.0

Subtask #4 25.0 / 25.0

Subtask #5 0 / 29.0

Subtask #1
9.0 / 9.0

Subtask #2
16.0 / 16.0

Subtask #3
21.0 / 21.0

Subtask #4
25.0 / 25.0

Subtask #5
0 / 29.0