Submission #354305

#	Time	Username	Problem	Language	Result	Execution time	Memory
354305		CaroLinda	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	122 ms	512 KiB

sculpture

#include <bits/stdc++.h>

#define ll long long
#define all(x) x.begin(),x.end()

const int MAX = 2010 ;
const int LOG = 43 ;

using namespace std ;

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

void solve1()
{

	vector<int> dp(n+1) ;

	long long mask = 0 ;

	for(int i = LOG-1 ; i >= 0 ; i-- )
	{
		dp[0] = 0 ;

		for(int j = 1 ; j <= n ; j++ )
		{
			ll curSum = 0LL ;
			dp[j] = n+1 ;

			for(int g = j ; g > 0 ; g-- )
			{
				curSum += arr[g] ;

				ll newMask = curSum >> i ;
				newMask <<= i ;

				if( (newMask|mask) == mask )				
					dp[j] = min(dp[j] , dp[g-1] + 1 ) ;
			}

		}

		if(dp[n] > b ) mask |= (1LL<<i) ;

	}
	
	printf("%lld\n", mask ) ;

}

void solveGeneral()
{
	
	vector< vector<bool> > dp(b+1, vector<bool>(n+1) ) ;

	ll mask= 0LL ;
	
	for(int i = 38 ; i >= 0 ; i-- )
	{

		for(int j = 1 ; j <= n ; j++ ) dp[0][j] = false ;
		dp[0][0] = true ;

		for(int qtdGroups = 1 ;qtdGroups <= b ; qtdGroups++ )
		{
			for(int j = 1 ; j <= n ; j++ ) 
			{
				dp[qtdGroups][j] = false ;

				ll curSum = 0LL ;

				for(int g = j ; g > 0 && !dp[qtdGroups][j] ; g-- )
				{
					curSum += arr[g] ;

					ll newMask = curSum >> i ;
					newMask <<= i ;

					if( (newMask|mask) == mask )
						dp[qtdGroups][j] = dp[qtdGroups-1][g-1] ;

				}

			}
		}

		bool ok = false ;
		for(int j = a ; j <= b ; j++ ) ok |= dp[j][n] ;

		if(!ok) mask |= (1LL<<i) ;

	}
		
	printf("%lld\n", mask ) ;


}

int main()
{
	
	scanf("%d %d %d", &n, &a, &b ) ;
	for(int i= 1 ; i <= n ;i++ ) scanf("%lld", &arr[i] ) ;

	if(a == 1 ) solve1() ;
	else solveGeneral() ;

}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:102:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  102 |  scanf("%d %d %d", &n, &a, &b ) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:103:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  103 |  for(int i= 1 ; i <= n ;i++ ) scanf("%lld", &arr[i] ) ;
      |                               ~~~~~^~~~~~~~~~~~~~~~~~

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