답안 #68367 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
68367	2018-08-16T20:43:07 Z	thebes	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	127 ms	2456 KB

sculpture

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MN=2002,LG=45;
ll N, A, B, ans, i, j, k, psa[MN], mn[MN];
bitset<MN> dp[MN];
bool idk(ll m){
	for(i=2;i<=N+1;i++) mn[i]=1<<30;
	for(i=1;i<=N;i++){
		for(j=i+1;j<=N+1;j++){
			if((m|(psa[j-1]-psa[i-1]))!=m) continue;
			mn[j] = min(mn[j], mn[i]+1);
		}
	}
	return mn[N+1]<=B;
}
bool check(ll m){
	if(A==1) return idk(m);
	for(i=1;i<=N;i++) dp[i].reset();
	dp[0][0] = 1;
	for(i=1;i<=N;i++){
		for(j=i;j>=1;j--){
			if((m|(psa[i]-psa[j-1]))!=m) continue;
			for(k=0;k<B;k++) if(dp[j-1][k]) dp[i][k+1]=1;
		}
	}
	for(i=A;i<=B;i++) if(dp[N][i]) return 1;
	return 0;
}

int main(){
	scanf("%lld%lld%lld",&N,&A,&B);
	for(i=1;i<=N;i++)
		scanf("%lld",&psa[i]),psa[i]+=psa[i-1];
	ans = (1LL<<LG)-1;
	for(int i=LG-1;i>=0;i--){
		ans -= (1LL<<i);
		if(!check(ans)) ans += 1LL<<i;
	}
	printf("%lld\n",ans);
	return 0;
}

Compilation message

sculpture.cpp: In function 'int main()':
sculpture.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld",&N,&A,&B);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:35:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&psa[i]),psa[i]+=psa[i-1];
   ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	3 ms	360 KB	Output is correct
3	Correct	2 ms	472 KB	Output is correct
4	Correct	2 ms	512 KB	Output is correct
5	Correct	2 ms	516 KB	Output is correct
6	Correct	2 ms	632 KB	Output is correct
7	Correct	2 ms	680 KB	Output is correct
8	Correct	2 ms	684 KB	Output is correct
9	Correct	3 ms	692 KB	Output is correct
10	Correct	2 ms	700 KB	Output is correct
11	Correct	3 ms	700 KB	Output is correct
12	Correct	2 ms	724 KB	Output is correct
13	Correct	2 ms	724 KB	Output is correct
14	Correct	2 ms	728 KB	Output is correct
15	Correct	3 ms	732 KB	Output is correct
16	Correct	2 ms	736 KB	Output is correct
17	Correct	2 ms	740 KB	Output is correct
18	Correct	3 ms	784 KB	Output is correct
19	Correct	2 ms	904 KB	Output is correct
20	Correct	2 ms	924 KB	Output is correct
21	Correct	3 ms	924 KB	Output is correct
22	Correct	2 ms	924 KB	Output is correct
23	Correct	2 ms	924 KB	Output is correct
24	Correct	3 ms	940 KB	Output is correct
25	Correct	2 ms	940 KB	Output is correct
26	Correct	2 ms	940 KB	Output is correct
27	Correct	2 ms	948 KB	Output is correct
28	Correct	2 ms	952 KB	Output is correct
29	Correct	3 ms	952 KB	Output is correct
30	Correct	2 ms	968 KB	Output is correct
31	Correct	3 ms	968 KB	Output is correct
32	Correct	2 ms	968 KB	Output is correct
33	Correct	3 ms	968 KB	Output is correct
34	Correct	3 ms	968 KB	Output is correct
35	Correct	3 ms	968 KB	Output is correct
36	Correct	2 ms	980 KB	Output is correct

Subtask #2
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	980 KB	Output is correct
2	Correct	2 ms	980 KB	Output is correct
3	Correct	3 ms	980 KB	Output is correct
4	Correct	3 ms	980 KB	Output is correct
5	Correct	3 ms	980 KB	Output is correct
6	Correct	3 ms	980 KB	Output is correct
7	Correct	2 ms	980 KB	Output is correct
8	Correct	2 ms	980 KB	Output is correct
9	Correct	2 ms	1020 KB	Output is correct
10	Correct	2 ms	1020 KB	Output is correct
11	Correct	3 ms	1020 KB	Output is correct
12	Correct	2 ms	1020 KB	Output is correct
13	Correct	2 ms	1020 KB	Output is correct
14	Correct	3 ms	1020 KB	Output is correct
15	Correct	3 ms	1020 KB	Output is correct
16	Correct	2 ms	1024 KB	Output is correct
17	Correct	3 ms	1024 KB	Output is correct
18	Correct	2 ms	1024 KB	Output is correct
19	Correct	3 ms	1024 KB	Output is correct
20	Correct	3 ms	1024 KB	Output is correct
21	Correct	3 ms	1024 KB	Output is correct
22	Correct	3 ms	1024 KB	Output is correct
23	Correct	3 ms	1024 KB	Output is correct
24	Correct	3 ms	1120 KB	Output is correct
25	Correct	4 ms	1120 KB	Output is correct
26	Correct	3 ms	1120 KB	Output is correct
27	Correct	3 ms	1120 KB	Output is correct
28	Correct	2 ms	1120 KB	Output is correct
29	Correct	3 ms	1120 KB	Output is correct
30	Correct	3 ms	1120 KB	Output is correct
31	Correct	3 ms	1120 KB	Output is correct
32	Correct	3 ms	1120 KB	Output is correct
33	Correct	2 ms	1120 KB	Output is correct
34	Correct	3 ms	1120 KB	Output is correct
35	Correct	3 ms	1120 KB	Output is correct
36	Correct	2 ms	1168 KB	Output is correct

Subtask #3
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1188 KB	Output is correct
2	Correct	2 ms	1188 KB	Output is correct
3	Correct	2 ms	1192 KB	Output is correct
4	Correct	2 ms	1196 KB	Output is correct
5	Correct	3 ms	1200 KB	Output is correct
6	Correct	3 ms	1204 KB	Output is correct
7	Correct	4 ms	1204 KB	Output is correct
8	Correct	3 ms	1212 KB	Output is correct
9	Correct	3 ms	1216 KB	Output is correct
10	Correct	3 ms	1220 KB	Output is correct
11	Correct	3 ms	1228 KB	Output is correct
12	Correct	2 ms	1228 KB	Output is correct
13	Correct	2 ms	1232 KB	Output is correct
14	Correct	2 ms	1236 KB	Output is correct
15	Correct	3 ms	1240 KB	Output is correct
16	Correct	3 ms	1244 KB	Output is correct
17	Correct	3 ms	1248 KB	Output is correct
18	Correct	3 ms	1260 KB	Output is correct
19	Correct	4 ms	1260 KB	Output is correct
20	Correct	3 ms	1260 KB	Output is correct
21	Correct	2 ms	1268 KB	Output is correct
22	Correct	2 ms	1276 KB	Output is correct
23	Correct	2 ms	1280 KB	Output is correct
24	Correct	3 ms	1288 KB	Output is correct
25	Correct	3 ms	1288 KB	Output is correct
26	Correct	3 ms	1292 KB	Output is correct
27	Correct	3 ms	1296 KB	Output is correct
28	Correct	3 ms	1300 KB	Output is correct
29	Correct	4 ms	1304 KB	Output is correct
30	Correct	3 ms	1308 KB	Output is correct
31	Correct	2 ms	1312 KB	Output is correct
32	Correct	3 ms	1316 KB	Output is correct

Subtask #4
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	1320 KB	Output is correct
2	Correct	2 ms	1324 KB	Output is correct
3	Correct	3 ms	1328 KB	Output is correct
4	Correct	2 ms	1456 KB	Output is correct
5	Correct	2 ms	1456 KB	Output is correct
6	Correct	3 ms	1456 KB	Output is correct
7	Correct	3 ms	1456 KB	Output is correct
8	Correct	3 ms	1476 KB	Output is correct
9	Correct	2 ms	1500 KB	Output is correct
10	Correct	3 ms	1500 KB	Output is correct
11	Correct	2 ms	1500 KB	Output is correct
12	Correct	2 ms	1500 KB	Output is correct
13	Correct	2 ms	1500 KB	Output is correct
14	Correct	2 ms	1500 KB	Output is correct
15	Correct	2 ms	1500 KB	Output is correct
16	Correct	3 ms	1500 KB	Output is correct
17	Correct	2 ms	1500 KB	Output is correct
18	Correct	2 ms	1500 KB	Output is correct
19	Correct	3 ms	1500 KB	Output is correct
20	Correct	3 ms	1500 KB	Output is correct
21	Correct	3 ms	1500 KB	Output is correct
22	Correct	3 ms	1500 KB	Output is correct
23	Correct	3 ms	1572 KB	Output is correct
24	Correct	2 ms	1572 KB	Output is correct
25	Correct	3 ms	1572 KB	Output is correct
26	Correct	3 ms	1572 KB	Output is correct
27	Correct	2 ms	1572 KB	Output is correct
28	Correct	2 ms	1572 KB	Output is correct
29	Correct	3 ms	1572 KB	Output is correct
30	Correct	2 ms	1572 KB	Output is correct
31	Correct	2 ms	1572 KB	Output is correct
32	Correct	2 ms	1572 KB	Output is correct
33	Correct	3 ms	1572 KB	Output is correct
34	Correct	2 ms	1572 KB	Output is correct
35	Correct	2 ms	1572 KB	Output is correct
36	Correct	3 ms	1572 KB	Output is correct
37	Correct	2 ms	1572 KB	Output is correct
38	Correct	2 ms	1572 KB	Output is correct
39	Correct	2 ms	1572 KB	Output is correct
40	Correct	2 ms	1572 KB	Output is correct
41	Correct	2 ms	1572 KB	Output is correct
42	Correct	2 ms	1572 KB	Output is correct
43	Correct	3 ms	1572 KB	Output is correct
44	Correct	2 ms	1572 KB	Output is correct
45	Correct	3 ms	1572 KB	Output is correct
46	Correct	2 ms	1572 KB	Output is correct
47	Correct	2 ms	1576 KB	Output is correct
48	Correct	3 ms	1576 KB	Output is correct
49	Correct	2 ms	1588 KB	Output is correct
50	Correct	2 ms	1588 KB	Output is correct
51	Correct	3 ms	1592 KB	Output is correct
52	Correct	2 ms	1592 KB	Output is correct
53	Correct	3 ms	1592 KB	Output is correct
54	Correct	2 ms	1600 KB	Output is correct
55	Correct	3 ms	1608 KB	Output is correct
56	Correct	3 ms	1612 KB	Output is correct
57	Correct	3 ms	1616 KB	Output is correct
58	Correct	3 ms	1652 KB	Output is correct
59	Correct	3 ms	1764 KB	Output is correct
60	Correct	3 ms	1764 KB	Output is correct
61	Correct	2 ms	1764 KB	Output is correct
62	Correct	2 ms	1764 KB	Output is correct
63	Correct	2 ms	1764 KB	Output is correct
64	Correct	32 ms	1764 KB	Output is correct
65	Correct	4 ms	1764 KB	Output is correct
66	Correct	4 ms	1808 KB	Output is correct
67	Correct	5 ms	1808 KB	Output is correct
68	Correct	9 ms	1808 KB	Output is correct
69	Correct	15 ms	1824 KB	Output is correct
70	Correct	13 ms	1824 KB	Output is correct
71	Correct	3 ms	1824 KB	Output is correct
72	Correct	17 ms	1824 KB	Output is correct
73	Correct	16 ms	1824 KB	Output is correct
74	Correct	14 ms	1824 KB	Output is correct

Subtask #5
29.0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	1824 KB	Output is correct
2	Correct	2 ms	1824 KB	Output is correct
3	Correct	2 ms	1824 KB	Output is correct
4	Correct	2 ms	1824 KB	Output is correct
5	Correct	2 ms	1824 KB	Output is correct
6	Correct	2 ms	1824 KB	Output is correct
7	Correct	2 ms	1824 KB	Output is correct
8	Correct	3 ms	1824 KB	Output is correct
9	Correct	3 ms	1860 KB	Output is correct
10	Correct	2 ms	1860 KB	Output is correct
11	Correct	2 ms	1860 KB	Output is correct
12	Correct	2 ms	1860 KB	Output is correct
13	Correct	2 ms	1860 KB	Output is correct
14	Correct	3 ms	1860 KB	Output is correct
15	Correct	2 ms	1860 KB	Output is correct
16	Correct	3 ms	1860 KB	Output is correct
17	Correct	2 ms	1860 KB	Output is correct
18	Correct	2 ms	1860 KB	Output is correct
19	Correct	2 ms	1860 KB	Output is correct
20	Correct	2 ms	1860 KB	Output is correct
21	Correct	3 ms	1860 KB	Output is correct
22	Correct	2 ms	1860 KB	Output is correct
23	Correct	2 ms	1860 KB	Output is correct
24	Correct	3 ms	1948 KB	Output is correct
25	Correct	2 ms	1948 KB	Output is correct
26	Correct	2 ms	1948 KB	Output is correct
27	Correct	2 ms	1948 KB	Output is correct
28	Correct	2 ms	1948 KB	Output is correct
29	Correct	2 ms	1948 KB	Output is correct
30	Correct	2 ms	1948 KB	Output is correct
31	Correct	3 ms	1948 KB	Output is correct
32	Correct	2 ms	1972 KB	Output is correct
33	Correct	2 ms	1976 KB	Output is correct
34	Correct	2 ms	1976 KB	Output is correct
35	Correct	2 ms	1976 KB	Output is correct
36	Correct	2 ms	1976 KB	Output is correct
37	Correct	3 ms	2008 KB	Output is correct
38	Correct	3 ms	2008 KB	Output is correct
39	Correct	2 ms	2024 KB	Output is correct
40	Correct	3 ms	2024 KB	Output is correct
41	Correct	3 ms	2024 KB	Output is correct
42	Correct	4 ms	2024 KB	Output is correct
43	Correct	2 ms	2024 KB	Output is correct
44	Correct	4 ms	2024 KB	Output is correct
45	Correct	3 ms	2024 KB	Output is correct
46	Correct	4 ms	2024 KB	Output is correct
47	Correct	2 ms	2024 KB	Output is correct
48	Correct	2 ms	2024 KB	Output is correct
49	Correct	4 ms	2024 KB	Output is correct
50	Correct	3 ms	2024 KB	Output is correct
51	Correct	2 ms	2024 KB	Output is correct
52	Correct	10 ms	2024 KB	Output is correct
53	Correct	16 ms	2024 KB	Output is correct
54	Correct	27 ms	2036 KB	Output is correct
55	Correct	28 ms	2192 KB	Output is correct
56	Correct	102 ms	2192 KB	Output is correct
57	Correct	102 ms	2192 KB	Output is correct
58	Correct	90 ms	2192 KB	Output is correct
59	Correct	88 ms	2192 KB	Output is correct
60	Correct	127 ms	2244 KB	Output is correct
61	Correct	3 ms	2244 KB	Output is correct
62	Correct	16 ms	2244 KB	Output is correct
63	Correct	28 ms	2244 KB	Output is correct
64	Correct	25 ms	2244 KB	Output is correct
65	Correct	52 ms	2252 KB	Output is correct
66	Correct	79 ms	2316 KB	Output is correct
67	Correct	100 ms	2316 KB	Output is correct
68	Correct	107 ms	2440 KB	Output is correct
69	Correct	94 ms	2456 KB	Output is correct

답안 #68367

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 29.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
29.0 / 29.0