Submission #317801

#	Time	Username	Problem	Language	Result	Execution time	Memory
317801		MahdiBahramian	Bali Sculptures (APIO15_sculpture)	C++11	100 / 100	136 ms	11160 KiB

sculpture

#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';
}

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