제출 #882786

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
882786		Kel_Mahmut	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	130 ms	2904 KiB

sculpture

#include<bits/stdc++.h>
#define pb push_back
#define endl ("\n")
#define all(aa) aa.begin(), aa.end()
typedef long long ll;
using namespace std;

const int maxn = 2005;

int n, l, r;
ll pref[maxn];
bool dp[maxn][maxn];
int dp1[maxn];
ll sum(int a, int b){
	return pref[b] - pref[a-1];
}

bool check(ll val){
	dp[0][0] = 1;

	for(int i = 1; i <= n; i++){
		for(int cnt = 1; cnt <= i; cnt++){
			dp[i][cnt] = 0;
			for(int j = 0; j < i; j++){
				if(dp[j][cnt-1] && ((val & sum(j+1, i)) == 0) )
					dp[i][cnt] = 1;
			}
		}
	}

	bool ret = 0;
	for(int i = l; i <= r; i++){
		ret |=dp[n][i];
	}
	return ret;
}

bool check1(ll val){
	dp1[0] = 0;
	for(int i = 1; i <= n; i++){
		dp1[i] = n+1;
		for(int j = 0; j < i; j++){
			if((sum(j+1, i) & val) == 0)
				dp1[i] = min(dp1[i], dp1[j] + 1);
		}
	}

	return (dp1[n] <= r);
}

int main(){
	cin >> n >> l >> r;
	for(int i = 1; i <= n; i++){
		cin >> pref[i]; pref[i]+=pref[i-1];
	}
	if(l != 1){
		ll cur = 0;
		for(int pw = 62; pw >= 0; pw--){
			if(check(cur + (1ll << pw))) cur+=(1ll<<pw);
		}
		cout << LONG_LONG_MAX - cur<< endl;
	} else{
		ll cur = 0;
		for(int pw = 62; pw >= 0; pw--){
			if(check1(cur + (1ll << pw))) cur+=(1ll<<pw);
		}
		cout << LONG_LONG_MAX - cur<< endl;

	}
}

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