Submission #812544

#	Time	Username	Problem	Language	Result	Execution time	Memory
812544		Belphegor	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	112 ms	344 KiB

sculpture

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll u = 1;
int n,a,b;
ll A[2005];
int dp[2005];
bitset<101>DP[105];

bool pos(ll mask){
	for(int i=1; i<=n; i++){
		dp[i] = 1e8;
		for(int j=0; j<i; j++){
			ll w = A[i] - A[j];
			if((w&mask) == w) dp[i] = min(dp[i],1 + dp[j]);
		}
	}
	return (dp[n] <= b);
}
bool pos2(ll mask){
	for(int i=0; i<=n; i++) DP[i].reset();
	DP[0][0] = 1;
	for(int i=1; i<=n; i++){
		for(int j=0; j<i; j++){
			ll w = A[i] - A[j];
			if((w&mask) == w) DP[i]|=(DP[j]<<1);
		}
	}
	for(int i=a; i<=b; i++) if(DP[n][i]) return 1;
	return 0;
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin>>n>>a>>b;
    for(int i=1; i<=n; i++) cin>>A[i];
    for(int i=1; i<=n; i++) A[i]+=A[i-1];
    if(!A[n]){
    	cout<<0;
    	return 0;
	}
    if(a > 1){
    	assert(n<=100);
    	int last_digit = 41;
    	while(pos2( (u<<(last_digit+1)) - 1 )) last_digit--;
		last_digit++;
		ll mask = (u<<last_digit)*2 - 1;
		for(int i=last_digit-1; i>=0; i--){
			mask^=(u<<i);
			if(pos2(mask)) continue;
			else mask^=(u<<i);
		}
		cout<<mask;
	}
	else{
		int last_digit = 41;
		while(pos( (u<<(last_digit+1)) - 1 )) last_digit--;
		last_digit++;
		ll mask = (u<<last_digit)*2 - 1;
		for(int i=last_digit-1; i>=0; i--){
			mask^=(u<<i);
			if(pos(mask)) continue;
			else mask^=(u<<i);
		}
		cout<<mask;
	}
}

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