oj.uz

Submission #32176

# Submission time Handle Problem Language Result Execution time Memory
32176 2017-10-03T01:26:31 Z minchurl Bali Sculptures (APIO15_sculpture) C++11
21 / 100
 0 ms 1144 KB 
#include<stdio.h>
#define LL long long
#define MAX_N 2005
#define inf (1LL<<60)
#define MIN(x,y) ((x)<(y)?(x):(y))
LL ans,e;
LL arr[MAX_N],t[MAX_N];
LL N,A,B;
bool is_ok(LL x){
	LL i,j,sum,y,z;
	for(i=1;i<=N;i++)	t[i]=inf;
	t[0]=0;
	if(x>=0)ans+=(1LL<<x);
	y=(ans&-ans);
	for(i=1;i<=N;i++){
		sum=0;
		for(j=i;j>=1;j--){
			sum+=arr[j];
			z=sum;
			if(x>=0){z=sum|(y-1);z++;z-=y;}
			z|=ans;
			if(z!=ans)	continue;
			t[i]=MIN(t[i],t[j-1]+1);
		}
	}
	if(x>=0)ans-=(1LL<<x);
	if(t[N]>B)	return false;
	else	return true;
}
LL bin_search(){
	LL s=0,mid;
	bool x;
	while(s<=e){
		mid=(s+e)/2;
		x=is_ok(mid);
		if(x==true){
			if(is_ok(mid-1)==false)	return mid;
			else	e=mid-1;
		}else{
			if(is_ok(mid+1)==true)	return mid+1;
			else	s=mid+1;
		}
	}
	return -1;
}
void special(){
	//나중에...
	return;
}
int main(){
	LL i,x;
	scanf("%lld %lld %lld",&N,&A,&B);
	for(i=1;i<=N;i++){
		scanf("%lld",&arr[i]);
	}
	if(A!=1){
		special();
		return 0;
	}
	e=51;
	ans=(1LL<<52);
	while(e>=0){
		x=bin_search();
		if(x==-1)	break;
		ans|=(1<<(x));
		e--;
	}
	ans-=(1LL<<52);
	printf("%lld\n",ans);
	return 0;
}

Compilation message

sculpture.cpp: In function 'int main()':
sculpture.cpp:52:34: 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:54:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&arr[i]);
                        ^

Subtask #1
0 / 9.0

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

Subtask #2
0 / 16.0

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

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1144 KB Output is correct
2 Correct 0 ms 1144 KB Output is correct
3 Correct 0 ms 1144 KB Output is correct
4 Correct 0 ms 1144 KB Output is correct
5 Correct 0 ms 1144 KB Output is correct
6 Correct 0 ms 1144 KB Output is correct
7 Correct 0 ms 1144 KB Output is correct
8 Correct 0 ms 1144 KB Output is correct
9 Correct 0 ms 1144 KB Output is correct
10 Correct 0 ms 1144 KB Output is correct
11 Correct 0 ms 1144 KB Output is correct
12 Correct 0 ms 1144 KB Output is correct
13 Correct 0 ms 1144 KB Output is correct
14 Correct 0 ms 1144 KB Output is correct
15 Correct 0 ms 1144 KB Output is correct
16 Correct 0 ms 1144 KB Output is correct
17 Correct 0 ms 1144 KB Output is correct
18 Correct 0 ms 1144 KB Output is correct
19 Correct 0 ms 1144 KB Output is correct
20 Correct 0 ms 1144 KB Output is correct
21 Correct 0 ms 1144 KB Output is correct
22 Correct 0 ms 1144 KB Output is correct
23 Correct 0 ms 1144 KB Output is correct
24 Correct 0 ms 1144 KB Output is correct
25 Correct 0 ms 1144 KB Output is correct
26 Correct 0 ms 1144 KB Output is correct
27 Correct 0 ms 1144 KB Output is correct
28 Correct 0 ms 1144 KB Output is correct
29 Correct 0 ms 1144 KB Output is correct
30 Correct 0 ms 1144 KB Output is correct
31 Correct 0 ms 1144 KB Output is correct
32 Correct 0 ms 1144 KB Output is correct

Subtask #4
0 / 25.0

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

Subtask #5
0 / 29.0

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