Submission #1133473

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133473		Math4Life2020	Bali Sculptures (APIO15_sculpture)	C++20	50 / 100	78 ms	328 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);
	}
}

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

Compilation message (stderr)

sculpture.cpp: In function 'bool qry(ll)':
sculpture.cpp:28:1: warning: control reaches end of non-void function [-Wreturn-type]
   28 | }
      | ^

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