제출 #317801

#제출 시각아이디문제언어결과실행 시간메모리
317801MahdiBahramianBali Sculptures (APIO15_sculpture)C++11
100 / 100
136 ms11160 KiB
#include<bits/stdc++.h>
#define pb push_back
#define ins insert
#define var auto
#define F first
#define S second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int LOG = 40;
const int Max = 2e3 + 10;
const int INF = 1000000000;
int n , a , b;
bool dp[Max][Max];
bool ok[Max][Max];
int Y[Max];
int dist[Max];
vector<int> N[Max];

bool Check(ll selected , ll newCheck)
{
	if(a > 1)
	{
		for(int i = 1; i <= n ; i++)
		{
			ll sum = 0;
			for(int j = i; j <= n ; j++)
			{
				sum += Y[j];
				ok[i][j] = (sum & (~selected)) < newCheck;
				//cout << ok[i][j] << " ";
			}
			//cout << '\n';
		}
		for(int i = 1; i <= n ; i++)
			for(int j = 1; j <= n ;j++)
				dp[i][j] = 0;

		dp[0][0] = true;
		for(int i = 1; i <= n ; i++)
		{
			dp[i][1] = ok[1][i];
			for(int j = 2; j <= b; j++)
			{
				for(int l = 1; l <= i ; l++)
					dp[i][j] |= dp[l - 1][j - 1] & ok[l][i];
			}
		}

		for(int i = a; i <= b; i++)
			if(dp[n][i])
				return true;

		return false;
	}
	else
	{
		for(int i = 1; i <= n ; i++)
		{
			dist[i] = INF;
			N[i].clear();
			ll sum = 0;
			for(int j = i; j <= n ; j++)
			{
				sum += Y[j];
				if((sum & (~selected)) < newCheck) //add edge i -> j + 1
					N[i].pb(j + 1);
			}
		}
		dist[n + 1] = INF;
		
		queue<int> bfs; bfs.push(1); dist[1] = 0;
		while(bfs.size())
		{
			int v = bfs.front();
			bfs.pop();
			for(var u : N[v])
			{
				if(dist[v] + 1 < dist[u])
				{
					dist[u] = dist[v] + 1;
					bfs.push(u);
				}
			}
		}

		return dist[n + 1] <= b;
	}
}

int main()
{
	cin >> n >> a >> b;
	for(int i = 1; i <= n ; i++)
		cin >> Y[i];

	ll selected = 0;
	for(ll check = (1ll << LOG) ; check > 0 ; check >>= 1)
		if(!Check(selected , check))
			selected |= check;

	cout << selected << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...