제출 #328143

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
328143		hivakarami	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	151 ms	512 KiB

sculpture

#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long int ll;
typedef long double doublel;
#define f first
#define s second
 
const int N = 3000 + 100;
const int sq = 200;
const ll mod =  1e9 + 7;
const ll inf = 1e16;	

int dp[N];
ll y[N];
bool d[200][200];




int main()
{
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);	
	
	
	int n, a, b;
	cin >> n >> a >> b;
	for(int i = 0; i < n; i++)
		cin >> y[i];
	
	
	if(a == 1)
	{
		ll ans = (1ll << 42)-1;
		//cout << ans << endl;
		for(int i = 41; i >= 0; i--)
		{
			ans ^= (1ll << i);
			//cout << ans << endl;
			
			for(int j = 0; j < n; j++)
			{
				dp[j] = b+1;
				ll sum = y[j];
				for(int k = j-1; k >= 0; k--)
				{
					if((ans | sum) == ans)
					{
						dp[j] = min(dp[j], 1 + dp[k]);
					}
					sum += y[k];
				}
				if((ans | sum) == ans)
					dp[j] = 1;
					
					
				
			}	
			
			if(dp[n-1] > b)
				ans ^= (1ll << i);
			
		}
			
			
		cout << ans << endl;
		
		return 0;
	}




	ll ans = (1ll << 42)-1;
	//cout << ans << endl;
	for(int t = 41; t >= 0; t--)
	{
		ans ^= (1ll << t);
		//cout << ans << endl;
		bool bol = false;
		for(int k = 1; k <= b; k++)
		{
			for(int i = 0; i < n; i++)
			{
				d[i][k] = false;
				ll sum = y[i];
				for(int j = i-1; j >= 0; j--)
				{
					if((ans|sum) == ans)
						d[i][k] |= d[j][k-1];
					sum += y[j];
				}
				
				if((ans|sum) == ans)
					d[i][1] = true;
					
			//	cout << i << ' ' << k << ' ' << d[i][k] << endl;	
			}
			
			if(k >= a)
				bol |= d[n-1][k];
			
		}
		if(!bol)
			ans ^= (1ll << t);	
	}
		
		
	cout << ans << endl;
		
	
    return 0;
}

 
 	
 	

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