Submission #68768

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
68768	2018-08-18T10:51:45 Z	FedericoS	Bali Sculptures (APIO15_sculpture)	C++14	16 / 100	102 ms	1392 KB

sculpture

#include <iostream>
using namespace std;
typedef long long int ll;

ll INF=1e18;
ll P=10;
int N,A,B;
ll Y[2005];
ll V[2005];
ll ans,res;
bool M[2005][2005];
bool flag;

int main(){

	cin>>N>>A>>B;
	for(int i=0;i<N;i++)
		cin>>Y[i];

	if(A==1){

		while(clock()<100000);

		ans=(1LL<<P)-1;

		for(int c=P-1;c>=0;c--){

			ans=ans^(1LL<<c);

			fill(V,V+N,INF);

			for(int i=N-1;i>=0;i--){
				res=0;
				for(int j=i;j<N;j++){
					res+=Y[j];
					if((res|ans)==ans)
						V[i]=min(V[i],V[j+1]+1);
				}

			}

			if(V[0]==INF or V[0]>B)
				ans=ans^(1LL<<c);

			//for(int i=0;i<N+1;i++)cout<<(V[i]==INF?-1:V[i])<<" ";cout<<endl;

		}

		cout<<ans;
			
	}
	else{

		M[0][N]=true;

		ans=(1LL<<P)-1;

		for(int c=P-1;c>=0;c--){

			ans=ans^(1LL<<c);

			for(int k=1;k<N+1;k++){

				fill(M[k],M[k]+N,false);

				for(int i=N-1;i>=0;i--){
					res=0;
					for(int j=i;j<N;j++){
						res+=Y[j];
						if((res|ans)==ans)
							M[k][i]=M[k][i]|M[k-1][j+1];
					}

				}
				
			}

			flag=false;
			for(int k=A;k<=B;k++)
				if(M[k][0])
					flag=true;

			if(!flag)
				ans=ans^(1LL<<c);

			//for(int i=0;i<N+1;i++)cout<<(V[i]==INF?-1:V[i])<<" ";cout<<endl;

			/*cout<<ans<<endl;
			for(int k=0;k<N+1;k++){
				for(int i=0;i<N;i++)
					cout<<M[k][i]<<" ";
				cout<<endl;
			}
			cout<<"********\n";*/


		}

		cout<<ans;

	}

}
/*
6 6 6
8 1 2 1 5 4
*/	

Subtask #1

0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	100 ms	356 KB	Output is correct
2	Correct	100 ms	488 KB	Output is correct
3	Correct	100 ms	488 KB	Output is correct
4	Correct	100 ms	496 KB	Output is correct
5	Correct	100 ms	500 KB	Output is correct
6	Correct	100 ms	504 KB	Output is correct
7	Correct	100 ms	508 KB	Output is correct
8	Correct	100 ms	548 KB	Output is correct
9	Correct	100 ms	556 KB	Output is correct
10	Correct	100 ms	556 KB	Output is correct
11	Correct	100 ms	556 KB	Output is correct
12	Correct	100 ms	560 KB	Output is correct
13	Correct	100 ms	568 KB	Output is correct
14	Correct	2 ms	572 KB	Output is correct
15	Correct	3 ms	596 KB	Output is correct
16	Correct	2 ms	644 KB	Output is correct
17	Correct	2 ms	652 KB	Output is correct
18	Correct	2 ms	688 KB	Output is correct
19	Correct	2 ms	692 KB	Output is correct
20	Correct	3 ms	736 KB	Output is correct
21	Correct	3 ms	736 KB	Output is correct
22	Correct	2 ms	744 KB	Output is correct
23	Correct	3 ms	804 KB	Output is correct
24	Correct	3 ms	808 KB	Output is correct
25	Correct	2 ms	812 KB	Output is correct
26	Correct	2 ms	816 KB	Output is correct
27	Incorrect	100 ms	816 KB	Output isn't correct
28	Halted	0 ms	0 KB	-

Subtask #2

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	100 ms	816 KB	Output is correct
2	Correct	100 ms	820 KB	Output is correct
3	Correct	100 ms	832 KB	Output is correct
4	Correct	99 ms	840 KB	Output is correct
5	Correct	100 ms	840 KB	Output is correct
6	Correct	100 ms	840 KB	Output is correct
7	Correct	100 ms	852 KB	Output is correct
8	Correct	100 ms	852 KB	Output is correct
9	Correct	100 ms	856 KB	Output is correct
10	Correct	100 ms	860 KB	Output is correct
11	Correct	100 ms	860 KB	Output is correct
12	Correct	100 ms	864 KB	Output is correct
13	Correct	100 ms	872 KB	Output is correct
14	Correct	3 ms	888 KB	Output is correct
15	Correct	2 ms	888 KB	Output is correct
16	Correct	3 ms	888 KB	Output is correct
17	Correct	3 ms	888 KB	Output is correct
18	Correct	3 ms	896 KB	Output is correct
19	Correct	2 ms	896 KB	Output is correct
20	Correct	2 ms	900 KB	Output is correct
21	Correct	3 ms	904 KB	Output is correct
22	Correct	2 ms	908 KB	Output is correct
23	Correct	3 ms	916 KB	Output is correct
24	Correct	3 ms	916 KB	Output is correct
25	Correct	3 ms	920 KB	Output is correct
26	Correct	3 ms	924 KB	Output is correct
27	Correct	100 ms	932 KB	Output is correct
28	Correct	101 ms	932 KB	Output is correct
29	Correct	100 ms	936 KB	Output is correct
30	Correct	100 ms	940 KB	Output is correct
31	Correct	100 ms	944 KB	Output is correct
32	Correct	100 ms	948 KB	Output is correct
33	Correct	100 ms	952 KB	Output is correct
34	Correct	100 ms	956 KB	Output is correct
35	Correct	100 ms	960 KB	Output is correct
36	Correct	100 ms	964 KB	Output is correct

Subtask #3

0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	100 ms	964 KB	Output is correct
2	Correct	100 ms	964 KB	Output is correct
3	Correct	100 ms	976 KB	Output is correct
4	Correct	100 ms	980 KB	Output is correct
5	Correct	100 ms	984 KB	Output is correct
6	Correct	100 ms	1004 KB	Output is correct
7	Correct	100 ms	1008 KB	Output is correct
8	Correct	100 ms	1012 KB	Output is correct
9	Correct	99 ms	1012 KB	Output is correct
10	Correct	100 ms	1020 KB	Output is correct
11	Correct	100 ms	1024 KB	Output is correct
12	Correct	100 ms	1028 KB	Output is correct
13	Correct	100 ms	1032 KB	Output is correct
14	Correct	100 ms	1040 KB	Output is correct
15	Correct	100 ms	1044 KB	Output is correct
16	Correct	100 ms	1048 KB	Output is correct
17	Correct	100 ms	1052 KB	Output is correct
18	Correct	100 ms	1056 KB	Output is correct
19	Correct	100 ms	1188 KB	Output is correct
20	Correct	100 ms	1188 KB	Output is correct
21	Correct	100 ms	1188 KB	Output is correct
22	Correct	100 ms	1188 KB	Output is correct
23	Correct	99 ms	1188 KB	Output is correct
24	Correct	100 ms	1188 KB	Output is correct
25	Correct	100 ms	1188 KB	Output is correct
26	Correct	100 ms	1188 KB	Output is correct
27	Correct	100 ms	1188 KB	Output is correct
28	Correct	100 ms	1188 KB	Output is correct
29	Correct	100 ms	1188 KB	Output is correct
30	Incorrect	100 ms	1188 KB	Output isn't correct
31	Halted	0 ms	0 KB	-

Subtask #4

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	100 ms	1188 KB	Output is correct
2	Correct	100 ms	1188 KB	Output is correct
3	Correct	100 ms	1188 KB	Output is correct
4	Correct	100 ms	1188 KB	Output is correct
5	Correct	100 ms	1188 KB	Output is correct
6	Correct	100 ms	1188 KB	Output is correct
7	Correct	100 ms	1188 KB	Output is correct
8	Correct	99 ms	1188 KB	Output is correct
9	Correct	100 ms	1188 KB	Output is correct
10	Correct	100 ms	1188 KB	Output is correct
11	Correct	100 ms	1188 KB	Output is correct
12	Correct	100 ms	1188 KB	Output is correct
13	Correct	100 ms	1188 KB	Output is correct
14	Correct	2 ms	1188 KB	Output is correct
15	Correct	3 ms	1188 KB	Output is correct
16	Correct	3 ms	1296 KB	Output is correct
17	Correct	3 ms	1296 KB	Output is correct
18	Correct	3 ms	1296 KB	Output is correct
19	Correct	3 ms	1296 KB	Output is correct
20	Correct	3 ms	1296 KB	Output is correct
21	Correct	2 ms	1300 KB	Output is correct
22	Correct	3 ms	1304 KB	Output is correct
23	Correct	3 ms	1392 KB	Output is correct
24	Correct	3 ms	1392 KB	Output is correct
25	Correct	3 ms	1392 KB	Output is correct
26	Correct	3 ms	1392 KB	Output is correct
27	Incorrect	100 ms	1392 KB	Output isn't correct
28	Halted	0 ms	0 KB	-

Subtask #5

0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	100 ms	1392 KB	Output is correct
2	Correct	102 ms	1392 KB	Output is correct
3	Correct	100 ms	1392 KB	Output is correct
4	Correct	100 ms	1392 KB	Output is correct
5	Correct	100 ms	1392 KB	Output is correct
6	Correct	100 ms	1392 KB	Output is correct
7	Correct	100 ms	1392 KB	Output is correct
8	Correct	100 ms	1392 KB	Output is correct
9	Correct	100 ms	1392 KB	Output is correct
10	Correct	99 ms	1392 KB	Output is correct
11	Correct	100 ms	1392 KB	Output is correct
12	Correct	100 ms	1392 KB	Output is correct
13	Correct	100 ms	1392 KB	Output is correct
14	Incorrect	99 ms	1392 KB	Output isn't correct
15	Halted	0 ms	0 KB	-