Submission #162500

#	Time	Username	Problem	Language	Result	Execution time	Memory
162500		HungAnhGoldIBO2020	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	269 ms	532 KiB

sculpture

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2002;
const int M=102;
const int inf=1e18+7;
int n,dp1[N],a,b;
int dp[M][M],sum[N],ar[N];
bool check(int val,int bit){
	for(int i=1;i<=n;i++){
		dp1[i]=inf;
		for(int j=0;j<i;j++){
			int k=sum[i]-sum[j];
			if(((val|k)>>bit)==(val>>bit)){
				dp1[i]=min(dp1[i],dp1[j]+1);
			}
		}
	}
	if(dp1[n]<=b){
		return true;
	}
	return false;
}
bool check1(int val,int bit){
	dp[0][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=b;j++){
			dp[i][j]=0;
		}
		for(int j=0;j<i;j++){
			int k=sum[i]-sum[j];
			if(((val|k)>>bit)==(val>>bit)){
				for(int l=1;l<=b;l++){
					dp[i][l]=dp[i][l]|dp[j][l-1];
				}
			}
		}
	}
	for(int i=a;i<=b;i++){
		if(dp[n][i]){
			return true;
		}
	}
	return false;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int i,j,k,l,ans=0;
	//cout<<ans<<endl;
	cin>>n>>a>>b;
	for(i=1;i<=n;i++){
		cin>>ar[i];
		sum[i]=sum[i-1]+ar[i];
	}
	if(a==1){
		for(i=63;i>-1;i--){
			if(!check(ans,i)){
				ans=ans|(1ll<<i);	
			}
		}
		cout<<ans;
	}
	else{
		for(i=63;i>-1;i--){
			if(!check1(ans,i)){
				ans=ans|(1ll<<i);
			}
		}
		cout<<ans;
	}
}
/*
6 2 3
8 1 2 1 5 4
*/

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:49:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j,k,l,ans=0;
        ^
sculpture.cpp:49:10: warning: unused variable 'k' [-Wunused-variable]
  int i,j,k,l,ans=0;
          ^
sculpture.cpp:49:12: warning: unused variable 'l' [-Wunused-variable]
  int i,j,k,l,ans=0;
            ^

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 21 / 21
• Subtask 4: 25 / 25
• Subtask 5: 29 / 29