Submission #563573

#	Time	Username	Problem	Language	Result	Execution time	Memory
563573		myrcella	Bali Sculptures (APIO15_sculpture)	C++17	21 / 100	1067 ms	1748 KiB

sculpture

//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

const int maxn = 2e3+10;

int n,A,B;
ll val[maxn];
bool dp1[maxn][maxn];
int dp2[maxn];

bool check(ll mask,ll cur) {
	if (A==1) {
		dp1[0][0]=1;
		rep(i,1,n+1) {
			rep(j,0,min(B+1,i+1)) {
				dp1[i][j] = 0;
				rep(k,0,i) {
					if (dp1[k][j-1]==1 and ((((val[i]-val[k])>>cur)|mask) == mask)) {
						dp1[i][j]=1;
						break;
					}
				}
				if (dp1[i][j]==1 and i==n and j>=A) return true;
			}
		}
		return false;
	}
	else {
		dp2[0] = 0;
		rep(i,1,n+1) {
			dp2[i] = B+1;
			rep(j,0,i) {
				if ((((val[i]-val[j])>>cur)|mask) == mask) dp2[i] = min(dp2[i],dp2[j]+1);
			}
			if (dp2[i]>B) return false;
		}
		return true;
	}
}

int main() {
//	freopen("input.txt","r",stdin);	
	std::ios::sync_with_stdio(false);cin.tie();
	cin>>n>>A>>B;
	val[0]=0;
	rep(i,1,n+1) cin>>val[i],val[i]+=val[i-1];
	ll mask = 0, cur = 40;
	while (cur>=0) {
		mask*=2;
		if (!check(mask,cur)) mask+=1;
		cur--;
	}
	cout<<mask;
	return 0;
}
/*
6 2 3
8 1 2 1 5 4
*/

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