Submission #1153224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153224		zhasyn	Bali Sculptures (APIO15_sculpture)	C++20	100 / 100	76 ms	332 KiB

sculpture

#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
using namespace std;
#define F first
#define S second
typedef long long ll;
#define pii pair <int, int>
#define pll pair <ll, ll>
typedef long double ld;
const ll N = 1e5 + 100, M = 4096 + 10, len = 21, inf = 1e18;
const ll mod = 1e9 + 7;

ll p[N], n, a, b, arr[N];
ll dp[N], nw[N];

void full(){
	ll x = 0, num = 0;
  	for(ll i = 40; i >= 0; i--){
  		//cout << i << " LL\n";
  		x += p[i];
  		num += p[i];
  		for(ll k = 1; k <= n; k++){
  			dp[k] = LLONG_MAX;
  		}
  		dp[0] = 0;
  		for(ll j = 1; j <= n; j++){
  			ll sum = 0;
  			//cout << j << " level\n";
  			for(ll k = j; k <= n; k++){
  				sum += arr[k];
  				if((sum & num) == 0 && dp[j - 1] != LLONG_MAX) dp[k] = min(dp[k], dp[j - 1] + 1);
  				//cout << dp[k] << " ";
  			}
  			//cout << endl;
  		}
  		if(dp[n] <= b) x -= p[i];
  		else num -= p[i];
  	}
  	cout << x;
}
int main(){
  	ios::sync_with_stdio(false);
  	cin.tie(NULL);
  	cin >> n >> a >> b;
  	for(ll i = 1; i <= n; i++){
  		cin >> arr[i];
  	}
  	
  	p[0] = 1LL;
  	for(ll i = 1; i <= 45; i++){
  		p[i] = p[i - 1] * 2LL;
  	}
  	if(a == 1){
  		full();
  		return 0;
  	}
  	ll x = 0, num = 0;
  	for(ll i = 40; i >= 0; i--){
  		x += p[i];
  		num += p[i];
  		for(ll k = 1; k <= n; k++){
  			dp[k] = 0;
  		}
  		dp[0] = 1;
  		//cout << i << " " << p[i] << " " << num << endl;
  		bool was = false;
  		for(ll gr = 1; gr <= b; gr++){
  			//cout << gr << " group\n";
  			for(ll j = gr; j <= n; j++){
  				if(dp[j - 1] == 0) continue;
  				ll sm = 0;
  				//cout << j << " " << dp[j - 1] << endl;
  				for(ll k = j; k <= n; k++){
  					sm += arr[k];
  					//cout << sm << endl;
  					if((sm & num) == 0) nw[k] = 1;
  				}
  			}
  			for(ll k = 1; k <= n; k++){
  				dp[k] = nw[k];
  				nw[k] = 0;
  			}
  			if(gr >= a && dp[n]) was = true;
  		}
  		if(was) x -= p[i];
  		else num -= p[i];
  		//cout << x << " "<< num << endl << endl;
  	}
  	cout << x;
  return 0;
}

 

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