Submission #1133475

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133475		Math4Life2020	Bali Sculptures (APIO15_sculpture)	C++20	100 / 100	61 ms	500 KiB

sculpture

#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";
}

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