Submission #1133475

#TimeUsernameProblemLanguageResultExecution timeMemory
1133475Math4Life2020Bali Sculptures (APIO15_sculpture)C++20
100 / 100
61 ms500 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;

const ll Nm = 2e3+5; ll N; const ll INF = 1e18;
ll Bmax = 42;
ll A,B;
vector<ll> Y;
ll psy[Nm+1];

bool qry(ll vq) {
	if (A==1) {
		vector<ll> dp(N+1,INF);
		dp[0]=0;
		for (ll i=0;i<N;i++) {
			if (dp[i]==INF) {
				continue;
			}
			for (ll j=(i+1);j<=N;j++) {
				ll yv = psy[j]-psy[i];
				if ((vq&yv)==yv) {
					dp[j]=min(dp[j],dp[i]+1);
				}
			}
		}
		return (dp[N]<=B);
	} else {
		bool dp[N+1][N+1];
		for (ll i=0;i<=N;i++) {
			for (ll j=0;j<=N;j++) {
				dp[i][j]=0;
			}
		}
		dp[0][0]=1;
		for (ll i=0;i<N;i++) {
			for (ll j=(i+1);j<=N;j++) {
				ll yv = psy[j]-psy[i];
				if ((vq&yv)==yv) {
					for (ll k=0;k<N;k++) {
						if (dp[i][k]) {
							dp[j][k+1]=1;
						}
					}
				}
			}
		}
		for (ll x=A;x<=B;x++) {
			if (dp[N][x]) {
				return 1;
			}
		}
		return 0;
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> N >> A >> B;
	psy[0]=0;
	for (ll t=0;t<N;t++) {
		ll y1; cin >> y1;
		Y.push_back(y1);
		psy[t+1]=psy[t]+y1;
	}
	ll ansF = 0; //ans fixed part
	for (ll b=Bmax;b>=0;b--) {
		//test no bit b, all bits <b
		ll vqry = ansF + (1LL<<b)-1;
		if (!qry(vqry)) { //0 -> bit subset of vqry impossible
			ansF += (1LL<<b);
		}
	}
	cout << ansF << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...