oj.uz

Submission #42092

# Submission time Handle Problem Language Result Execution time Memory
42092 2018-02-22T13:05:31 Z minchurl Bali Sculptures (APIO15_sculpture) C++11
0 / 100
 2 ms 532 KB 
#include<bits/stdc++.h>
#define MAX_N 2005
#define inf (1LL<<60)
#define LL long long
using namespace std;
LL n,a,b,ans,arr[MAX_N];
LL t[MAX_N],ct[MAX_N][MAX_N];
LL case1(){
	LL i,j,k,sum;
	for(i=0;i<=n;i++)	for(j=0;j<=n;j++)	ct[i][j]=inf;
	ans=inf;
	ct[0][0]=0;
	for(i=1;i<=n;i++){
		for(j=1;j<=i;j++){
			sum=0;
			for(k=i;k>=1;k--){
				sum+=arr[k];
				ct[j][i]=min(ct[j][i],ct[j-1][k-1]|sum);
				if(i==n && j>=a && j<=b)	ans=min(ans,ct[j][i]);
			}
		}
	}
	return ans;
}
bool is_ok(LL x){
	LL i,j,sum,test,y,z,k;
	y=inf-1;y-=(1LL<<x)-1;
	z=ans&y;
	for(i=1;i<=n;i++)	t[i]=inf;
	t[0]=0;
	for(i=1;i<=n;i++){
		sum=0;
		for(j=i;j>=1;j--){
			sum+=arr[j];
			k=sum&y;
			if((z|k)==z)	t[i]=min(t[i],t[j-1]+1);
		}
	}
	return t[n]<=b;
}
int main(){
	LL i,x;
	scanf("%lld",&n);
	scanf("%lld %lld",&a,&b);
	for(i=1;i<=n;i++)	scanf("%lld",&arr[i]);
	if(n<=100)	return !printf("%lld\n",case1());
	ans=0;
	for(i=50;i>=0;i--)	ans|=is_ok(i)?0LL:(1LL<<i);
	printf("%lld\n",ans);
	return 0;
}

Compilation message

sculpture.cpp: In function 'bool is_ok(long long int)':
sculpture.cpp:26:13: warning: unused variable 'test' [-Wunused-variable]
  LL i,j,sum,test,y,z,k;
             ^
sculpture.cpp: In function 'int main()':
sculpture.cpp:42:7: warning: unused variable 'x' [-Wunused-variable]
  LL i,x;
       ^
sculpture.cpp:43:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
                  ^
sculpture.cpp:44:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld",&a,&b);
                          ^
sculpture.cpp:45:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1;i<=n;i++) scanf("%lld",&arr[i]);
                                         ^

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Incorrect 1 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 424 KB Output is correct
2 Incorrect 2 ms 424 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 440 KB Output is correct
2 Incorrect 2 ms 440 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 500 KB Output is correct
2 Incorrect 2 ms 500 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 532 KB Output is correct
2 Incorrect 1 ms 532 KB Output isn't correct
3 Halted 0 ms 0 KB -