Submission #463811

#	Time	Username	Problem	Language	Result	Execution time	Memory
463811		MohamedAhmed04	Bali Sculptures (APIO15_sculpture)	C++14	37 / 100	28 ms	364 KiB

sculpture

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 100 + 10 ;

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

int 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 check()
{
	memset(dp , -1 , sizeof(dp)) ;
	return (solve(0 , 0) == 1) ;
}


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] ;
	for(int bit = 29 ; bit >= 0 ; --bit)
	{
		mask |= (1 << bit) ;
		if(!check())
			mask ^= (1 << bit) , ans += (1 << bit) ;
	}
	return cout<<ans<<"\n" , 0 ;
}

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