제출 #261361

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
261361		uacoder123	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	216 ms	888 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) lli(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))

typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <lli,ii> iii;
typedef vector <lli> vi;
lli n,a,b;
lli dp[2001],dp2[2001][2001],arr[2001];
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin>>n>>a>>b;
  for(lli i=0;i<n;++i)
  	cin>>arr[i];
  lli cur=0;
  if(a==1)
  {
  	for(lli i=50;i>=0;--i)
  	{
  		cur+=(1LL<<i);
  		for(lli j=0;j<n;++j)
  		{
  			lli s=0;
  			dp[j]=100000;
  			for(lli k=j;k>=0;--k)
  			{
  				s+=arr[k];
  				if((cur&s)==0)
  					dp[j]=min(dp[j],1+((k==0)?0:dp[k-1]));
  			}
  		}
  		if(dp[n-1]>b)
  			cur-=(1LL<<i);
  	}
  }
  else
  {
  	for(lli i=50;i>=0;--i)
  	{
  		cur+=(1LL<<i);
  		for(lli j=0;j<n;++j)
  		{
  			for(lli k=0;k<=b;++k)
  			{
  				lli s=0;
  				dp2[j][k]=0;
  				if(k==0)
  					continue;
  				for(lli l=j;l>=0;--l)
  				{
  					s+=arr[l];
  					if((cur&s)==0)
  					{
  						if(l==0)
  						{
  							if(k==1)
  								dp2[j][k]=1;
  						}
  						else
  							dp2[j][k]=max(dp2[j][k],dp2[l-1][k-1]);
  					}
  				}
  			}
  		}
  		lli ch=0;
  		for(lli j=a;j<=b;++j)
  			ch=max(dp2[n-1][j],ch);
  		if(!ch)
  			cur-=(1LL<<i);
  	}
  }
  cout<<(cur^2251799813685247)<<endl;
  return(0);
}

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