Submission #1185348

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185348		boclobanchat	Bali Sculptures (APIO15_sculpture)	C++20	50 / 100	120 ms	23300 KiB

sculpture

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2024;
long long F[MAXN][MAXN],dp[MAXN];
bool ck[MAXN][MAXN];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,a,b;
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++)
	{
		cin>>F[i][i];
		for(int j=i-1;j;j--) F[j][i]=F[j+1][i]+F[j][j];
	}
	long long ans=0;
	for(int i=41;i+1;i--)
	{
		long long res=ans|(1LL<<i);
		if(a==1)
		{
			for(int j=1;j<=n;j++)
			{
				dp[j]=1e9;
				for(int k=j-1;k+1;k--) if((F[k+1][j]&res)==0) dp[j]=min(dp[j],dp[k]+1);
			}
			if(dp[n]<=b) ans=res;
		}
		else
		{
			bool e=false;
			ck[0][0]=true;
			for(int j=0;j<=n;j++) for(int k=0;k<=n;k++) ck[j][k]=false;
			for(int j=1;j<=n;j++) for(int k=j-1;k+1;k--) if((F[k+1][j]&res)==0) for(int l=1;l<=n;l++) ck[j][l]|=ck[k][l-1];
			for(int j=a;j<=b;j++) e|=ck[n][j];
			if(e) ans=res;
		}
	}
	cout<<(1LL<<42)-1-ans;
}

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