Submission #882808

#	Time	Username	Problem	Language	Result	Execution time	Memory
882808		NotLinux	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	86 ms	600 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2005;
int n,a,b,y[N],pre[N];
bool check1(int past){
	bool dp[n+1][n+1];
	memset(dp , 0 , sizeof(dp));
	dp[0][0] = 1;
	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=n;j++){
			for(int k = i-1;k>=0;k--){
				int range_sum = pre[i] - pre[k];
				dp[i][j] |= dp[k][j-1] & ((range_sum & past) == 0);
			}
		}
	}
	for(int i = a;i<=b;i++){
		if(dp[n][i]){
			return 1;
		}
	}
	return 0;
}
bool check2(int past){
	int dp[n+1];
	memset(dp , -1 , sizeof(dp));
	dp[0] = 0;
	for(int i = 1;i<=n;i++){
		for(int j = i-1;j>=0;j--){
			int range_sum = pre[i] - pre[j];
			if(dp[j] != -1 and (range_sum & past) == 0){
				if(dp[i] == -1 or dp[i] > (dp[j]+1)){
					dp[i] = dp[j]+1;
				}
			}
		}
	}
	return (dp[n] != -1 and dp[n] <= b);
}
void solve(){
	cin >> n >> a >> b;
	for(int i = 0;i<n;i++){
		cin >> y[i];
	}   
	for(int i = 0;i<n;i++){
		pre[i+1] = pre[i] + y[i];
	}
	int dont = 0 , ans = 0;
	if(a > 1){
		for(int i = 40;i>=0;i--){
			if(check1(dont + (1ll<<i))){//olmadan da oluyor
				dont += 1ll << i;
			}
			else{//olmadan olmuyor
				ans += 1ll << i;
			}
		}
		cout << ans << endl;
	}
	else{
		for(int i = 40;i>=0;i--){
			if(check2(dont + (1ll<<i))){
				dont += 1ll << i;
			}
			else{
				ans  += 1ll << i;
			}
		}
		cout << ans << endl;
	}
}
signed main(){
		ios_base::sync_with_stdio(0);cin.tie(0);
		int testcase = 1;//cin >> testcase;
		while(testcase--)solve();
}

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