Submission #14387

#	Time	Username	Problem	Language	Result	Execution time	Memory
14387		woqja125	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	827 ms	8944 KiB

sculpture

#include<stdio.h>
#include<string.h>
int y[2001];
long long s[2001];
bool t1[2001][2001];
bool t2[2001][2001];
long long min(long long a, long long b){if(a<b)return a; return b;}
bool chk();
int n, a, b;
int main()
{
	int i, j;
	scanf("%d%d%d", &n, &a, &b);
	for(i=1; i<=n; i++)scanf("%d", y+i);
	for(i=1; i<=n; i++) s[i] = s[i-1] + y[i];
	for(i=1; i<=n; i++)for(j=i; j<=n; j++) t1[i][j] = true;
	long long ans = 0;
	for(int B=50; B>=0; B--)
	{
		for(i=1; i<=n; i++)for(j=1; j<=n; j++) t2[i][j] = t1[i][j];
		for(i=1; i<=n; i++) for(j=i; j<=n; j++) if( ((s[j] - s[i-1])&(1ll<<B)) != 0 ) t2[i][j] = false;
		if(chk())
		{
			for(i=1; i<=n; i++)for(j=1; j<=n; j++) t1[i][j] = t2[i][j];
		}
		else ans += (1ll<<B);
	}
	printf("%lld\n", ans);
	return 0;
}

bool chk1();
bool chk2();
bool chk()
{
	if(a!=1) return chk1();
	else return chk2();
}

bool dp[101][101];
bool chk1()
{
	int i, j, k;
	memset(dp, 0, sizeof(dp));
	dp[0][0] = true;
	for(i=0; i<b; i++)for(j=0; j<n; j++)
	{
		if(!dp[i][j]) continue;
		for(k=j+1; k<=n; k++)
		{
			if(t2[j+1][k] == true) dp[i+1][k] = true;
		}
	}
	for(i=a; i<=b; i++) if(dp[i][n]) return true;
	return false;
}

int d[2001];
bool chk2()
{
	int i, j;
	for(i=1; i<=n; i++) d[i] = 10000;
	for(i=0; i<n; i++)
	{
		for(j=i+1; j<=n; j++) if(t2[i+1][j]) d[j] = min(d[j], d[i]+1);
	}
	return d[n]<=b;
}

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