Submission #531026

#	Time	Username	Problem	Language	Result	Execution time	Memory
531026		new_acc	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	140 ms	752 KiB

sculpture

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<ll> vl;
const int N=2e3+10;
int dp[N];
int dp2[N][N],t[N];
int n,a,b;
int single(ll curr){
	for(int i=n;i>=1;i--){
		ll sum=0;
		dp[i]=n+1;
		for(int j=i;j<=n;j++){
			sum+=t[j];
			if((sum|curr)==curr) dp[i]=min(dp[i],dp[j+1]+1);
		}
	}
	return dp[1];
}
int single2(ll curr){
	for(int i=1;i<=n;i++) dp2[n+1][i]=n+1;
	for(int i=n;i>=1;i--){
		for(int j=1;j<=n;j++){
			dp2[i][j]=n+1;
			ll sum=0;
			for(int k=i;k<=n;k++){
				sum+=t[k];
				if((sum|curr)==curr){
					if(j-1==0){
						if(k+1==n+1) dp2[i][j]=1;
						else dp2[i][j]=min(dp2[i][j],dp2[k+1][1]+1);
					}else dp2[i][j]=min(dp2[i][j],dp2[k+1][j-1]+1);
				}
			}
		}
	}
	return dp2[1][a];
}
void solve(){
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++) cin>>t[i];
	if(a==1){
		ll curr=(1LL<<50)-1;
		for(int i=49;i>=0;i--) if(single(curr-(1LL<<i))<=b) curr-=(1LL<<i);
		cout<<curr<<"\n";
	}else{
		ll curr=(1LL<<50)-1;
		for(int i=49;i>=0;i--) if(single2(curr-(1LL<<i))<=b) curr-=(1LL<<i);
		cout<<curr<<"\n";
	}
}
int main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	solve();
}

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