Submission #463814

#	Time	Username	Problem	Language	Result	Execution time	Memory
463814		MohamedAhmed04	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	235 ms	16072 KiB

sculpture

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 2004 ;

int arr[MAX] ;
int n , a , b ;

long long mask , ans ;

int dp[MAX][MAX] ;

int solve(int idx , int groups)
{
	if(groups > b)
		return 0 ;
	if(idx == n)
		return (groups >= a && groups <= b) ;
	int &ret = dp[idx][groups] ;
	if(ret != -1)
		return ret ;
	ret = 0 ;
	long long sum = 0 ;
	for(int i = idx ; i < n ; ++i)
	{
		sum += arr[i] ;
		if((sum & mask))
			continue ;
		ret |= solve(i+1 , groups+1) ;
	}
	return ret ;
}

bool check1()
{
	memset(dp , -1 , sizeof(dp)) ;
	return (solve(0 , 0) == 1) ;
}

void calc1()
{
	for(int bit = 50 ; bit >= 0 ; --bit)
	{
		mask |= (1ll << bit) ;
		if(!check1())
			mask ^= (1ll << bit) , ans += (1ll << bit) ;
	}
}

int dp2[MAX] ;

int solve2(int idx)
{
	if(idx == n)
		return 0 ;
	int &ret = dp2[idx] ;
	if(ret != -1)
		return ret ;
	ret = 1e9 ;
	long long sum = 0 ;
	for(int i = idx ; i < n ; ++i)
	{
		sum += arr[i] ;
		if((sum & mask))
			continue ;
		ret = min(ret , solve2(i+1) + 1) ;
	}
	return ret ;
}

bool check2()
{
	memset(dp2 , -1 , sizeof(dp2)) ;
	return (solve2(0) <= b) ;
}

void calc2()
{
	for(int bit = 50 ; bit >= 0 ; --bit)
	{
		mask |= (1ll << bit) ;
		if(!check2())
			mask ^= (1ll << bit) , ans += (1ll << bit) ;
	}	
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>a>>b ;
	for(int i = 0 ; i < n ; ++i)
		cin>>arr[i] ;
	if(a > 1)
		calc1() ;
	else
		calc2() ;
	return cout<<ans<<"\n" , 0 ;
}

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