Submission #162499

#	Time	Username	Problem	Language	Result	Execution time	Memory
162499		HungAnhGoldIBO2020	Bali Sculptures (APIO15_sculpture)	C++14	50 / 100	372 ms	504 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;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int i,j,k,l,ans=(1ll<<32)-1;
	//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){
		ans=0;
		for(i=63;i>-1;i--){
			if(!check(ans,i)){
				ans=ans|(1ll<<i);	
			}
		}
		cout<<ans;
	}
	else{
		for(i=1;i<=n;i++){
			for(j=0;j<=b;j++){
				dp[i][j]=inf;
			}
			for(j=0;j<i;j++){
				for(k=1;k<=b;k++){
					dp[i][k]=min(dp[i][k],dp[j][k-1]|(sum[i]-sum[j]));
				}
			}
		}
		for(j=a;j<=b;j++){
			ans=min(ans,dp[n][j]);
		}
		cout<<ans;
	}
}
/*
6 1 3
8 1 2 1 5 4
*/

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:27:12: warning: unused variable 'l' [-Wunused-variable]
  int i,j,k,l,ans=(1ll<<32)-1;
            ^

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