답안 #205294

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
205294	2020-02-28T13:04:10 Z	kshitij_sodani	Bali Sculptures (APIO15_sculpture)	C++17	37 / 100	738 ms	80760 KB

sculpture

#include <iostream>
#include <bits/stdc++.h>
 
using namespace std;
typedef long long int llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#define endl "\n"
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n,a,b;
	cin>>n>>a>>b;
	int it[n];
	for(int i=0;i<n;i++){
		cin>>it[i];
	}
	int sa=2049;
	int dp[n][n][sa];
	memset(dp,0,sizeof(dp));
/*	vector<int> mm[sa];
	vector<int> nn[sa];
	for(int mask=0;mask<sa;mask++){
		for(int submask = mask; ; submask = (submask - 1) & mask) {
	        mm[mask].pb(submask);
	        nn[submask].pb(mask);
	        if(submask == 0) break;
		}
	}*/
	

	dp[0][0][it[0]]=1;
	/*for(int i=0;i<mm[it[0]].size();i++){
		dp[0][0][mm[it[0]]][i]=1;
	}*/
	int pre[n];
	pre[0]=it[0];
	for(int i=1;i<n;i++){
		pre[i]=pre[i-1]+it[i];
	}
	
	for(int i=1;i<n;i++){

		for(int j=0;j<i+1;j++){
			if(j==0){
				dp[i][0][pre[i]]=1;
				/*if(pre[i]==0){
					//cout<<i<<" "<<j<<endl;
				}*/
				continue;
			}
			for(int k=0;k<i;k++){
				for(int l=0;l<sa;l++){
					if(dp[k][j-1][l]==1){
						int no=(pre[i]-pre[k])|l;
						/*if(no==0){
							//cout<<"NNNNNNNNNNN"<<endl;
						}*/
						dp[i][j][no]=1;
					//	//cout<<no<<endl;
						/*if(i==n-1){
							//cout<<no<<endl;
							

						}*/
					}
				}
			}
		}
	//	//cout<<dp[5][1][0]<<":::::::::::::::::"<<endl;
	}
	int ma=sa;
	for(int i=a-1;i<b;i++){
		for(int j=0;j<sa;j++){
			////cout<<n-1<<" "<<i<<" "<<j<<" "<<dp[n-1][i][j]<<endl;
			if(dp[n-1][i][j]==1){
				/*if(j<ma){
					//cout<<i<<" "<<j<<endl;
				}*/
				ma=min(ma,j);
			}
		}
	}
	cout<<ma<<endl;
	/*int nno=8|3;
	//cout<<nno<<endl;
 
 
 */
 
 
	return 0;
}

Subtask #1

0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	632 KB	Output is correct
2	Correct	5 ms	760 KB	Output is correct
3	Correct	5 ms	376 KB	Output is correct
4	Correct	5 ms	504 KB	Output is correct
5	Correct	6 ms	1144 KB	Output is correct
6	Correct	7 ms	2168 KB	Output is correct
7	Correct	8 ms	2680 KB	Output is correct
8	Correct	10 ms	3576 KB	Output is correct
9	Correct	12 ms	3576 KB	Output is correct
10	Correct	11 ms	3576 KB	Output is correct
11	Correct	11 ms	3576 KB	Output is correct
12	Correct	10 ms	3580 KB	Output is correct
13	Correct	11 ms	3576 KB	Output is correct
14	Correct	5 ms	632 KB	Output is correct
15	Correct	5 ms	632 KB	Output is correct
16	Correct	5 ms	632 KB	Output is correct
17	Correct	5 ms	504 KB	Output is correct
18	Correct	5 ms	1144 KB	Output is correct
19	Correct	7 ms	2168 KB	Output is correct
20	Correct	8 ms	2640 KB	Output is correct
21	Correct	11 ms	3576 KB	Output is correct
22	Correct	11 ms	3576 KB	Output is correct
23	Correct	11 ms	3576 KB	Output is correct
24	Correct	10 ms	3576 KB	Output is correct
25	Correct	10 ms	3576 KB	Output is correct
26	Correct	11 ms	3576 KB	Output is correct
27	Runtime error	5 ms	888 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
28	Halted	0 ms	0 KB	-

Subtask #2

16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	632 KB	Output is correct
2	Correct	5 ms	892 KB	Output is correct
3	Correct	5 ms	376 KB	Output is correct
4	Correct	5 ms	504 KB	Output is correct
5	Correct	6 ms	1144 KB	Output is correct
6	Correct	8 ms	2168 KB	Output is correct
7	Correct	9 ms	2604 KB	Output is correct
8	Correct	11 ms	3576 KB	Output is correct
9	Correct	11 ms	3576 KB	Output is correct
10	Correct	11 ms	3576 KB	Output is correct
11	Correct	11 ms	3576 KB	Output is correct
12	Correct	10 ms	3576 KB	Output is correct
13	Correct	11 ms	3576 KB	Output is correct
14	Correct	5 ms	632 KB	Output is correct
15	Correct	5 ms	632 KB	Output is correct
16	Correct	5 ms	632 KB	Output is correct
17	Correct	5 ms	504 KB	Output is correct
18	Correct	6 ms	1144 KB	Output is correct
19	Correct	7 ms	2168 KB	Output is correct
20	Correct	8 ms	2680 KB	Output is correct
21	Correct	11 ms	3576 KB	Output is correct
22	Correct	11 ms	3576 KB	Output is correct
23	Correct	10 ms	3576 KB	Output is correct
24	Correct	11 ms	3576 KB	Output is correct
25	Correct	11 ms	3576 KB	Output is correct
26	Correct	11 ms	3576 KB	Output is correct
27	Correct	12 ms	3832 KB	Output is correct
28	Correct	17 ms	5368 KB	Output is correct
29	Correct	42 ms	11896 KB	Output is correct
30	Correct	56 ms	14456 KB	Output is correct
31	Correct	99 ms	20428 KB	Output is correct
32	Correct	98 ms	20344 KB	Output is correct
33	Correct	95 ms	20344 KB	Output is correct
34	Correct	93 ms	20348 KB	Output is correct
35	Correct	96 ms	20348 KB	Output is correct
36	Correct	98 ms	20344 KB	Output is correct

Subtask #3

21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	632 KB	Output is correct
2	Correct	5 ms	888 KB	Output is correct
3	Correct	5 ms	376 KB	Output is correct
4	Correct	5 ms	504 KB	Output is correct
5	Correct	6 ms	1144 KB	Output is correct
6	Correct	8 ms	2168 KB	Output is correct
7	Correct	8 ms	2680 KB	Output is correct
8	Correct	11 ms	3576 KB	Output is correct
9	Correct	11 ms	3576 KB	Output is correct
10	Correct	11 ms	3576 KB	Output is correct
11	Correct	13 ms	3576 KB	Output is correct
12	Correct	11 ms	3576 KB	Output is correct
13	Correct	11 ms	3576 KB	Output is correct
14	Correct	11 ms	3832 KB	Output is correct
15	Correct	16 ms	5368 KB	Output is correct
16	Correct	46 ms	11896 KB	Output is correct
17	Correct	58 ms	14456 KB	Output is correct
18	Correct	93 ms	20344 KB	Output is correct
19	Correct	96 ms	20344 KB	Output is correct
20	Correct	94 ms	20344 KB	Output is correct
21	Correct	101 ms	20344 KB	Output is correct
22	Correct	92 ms	20480 KB	Output is correct
23	Correct	94 ms	20344 KB	Output is correct
24	Correct	102 ms	21240 KB	Output is correct
25	Correct	205 ms	34296 KB	Output is correct
26	Correct	359 ms	49144 KB	Output is correct
27	Correct	547 ms	66680 KB	Output is correct
28	Correct	738 ms	80760 KB	Output is correct
29	Correct	700 ms	80632 KB	Output is correct
30	Correct	706 ms	80504 KB	Output is correct
31	Correct	730 ms	80632 KB	Output is correct
32	Correct	731 ms	80632 KB	Output is correct

Subtask #4

0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	632 KB	Output is correct
2	Correct	5 ms	888 KB	Output is correct
3	Correct	5 ms	376 KB	Output is correct
4	Correct	5 ms	504 KB	Output is correct
5	Correct	6 ms	1144 KB	Output is correct
6	Correct	9 ms	2168 KB	Output is correct
7	Correct	9 ms	2680 KB	Output is correct
8	Correct	11 ms	3576 KB	Output is correct
9	Correct	11 ms	3576 KB	Output is correct
10	Correct	13 ms	3576 KB	Output is correct
11	Correct	11 ms	3576 KB	Output is correct
12	Correct	10 ms	3576 KB	Output is correct
13	Correct	11 ms	3576 KB	Output is correct
14	Correct	5 ms	632 KB	Output is correct
15	Correct	5 ms	636 KB	Output is correct
16	Correct	5 ms	632 KB	Output is correct
17	Correct	5 ms	504 KB	Output is correct
18	Correct	6 ms	1144 KB	Output is correct
19	Correct	7 ms	2168 KB	Output is correct
20	Correct	8 ms	2680 KB	Output is correct
21	Correct	11 ms	3576 KB	Output is correct
22	Correct	11 ms	3576 KB	Output is correct
23	Correct	16 ms	3576 KB	Output is correct
24	Correct	11 ms	3576 KB	Output is correct
25	Correct	11 ms	3576 KB	Output is correct
26	Correct	10 ms	3576 KB	Output is correct
27	Runtime error	5 ms	888 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
28	Halted	0 ms	0 KB	-

Subtask #5

0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	632 KB	Output is correct
2	Correct	5 ms	760 KB	Output is correct
3	Correct	5 ms	376 KB	Output is correct
4	Correct	5 ms	504 KB	Output is correct
5	Correct	6 ms	1144 KB	Output is correct
6	Correct	7 ms	2168 KB	Output is correct
7	Correct	8 ms	2680 KB	Output is correct
8	Correct	15 ms	3576 KB	Output is correct
9	Correct	12 ms	3576 KB	Output is correct
10	Correct	11 ms	3576 KB	Output is correct
11	Correct	10 ms	3576 KB	Output is correct
12	Correct	11 ms	3576 KB	Output is correct
13	Correct	11 ms	3576 KB	Output is correct
14	Runtime error	5 ms	888 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
15	Halted	0 ms	0 KB	-