Submission #766516

#	Time	Username	Problem	Language	Result	Execution time	Memory
766516		1ne	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	539 ms	856 KiB

sculpture

#include<bits/stdc++.h>
using namespace std;
const int mxn = 2002; 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	long long n,a,b;cin>>n>>a>>b;
	vector<long long>arr(n);
	for (long long i = 0;i<n;++i){
		cin>>arr[i];
	}
	vector<long long>pref(n + 1,0);
	for (int i = 0;i<n;++i){
		pref[i + 1] = pref[i] + arr[i];
	}
	auto query = [&](int u,int v){
	  return pref[v + 1] - pref[u];
	};
	auto check = [&](long long v){
		bitset<mxn>dp[mxn + 1];
		dp[0][0] = 1;
		for (int i = 0;i<n;++i){
			bitset<mxn>cur;
			for (int j = 0;j<=n;++j){
				if (dp[i][j] == 1){
					cur[j + 1] = 1;
				}
			}
			for (int x = i;x<n;++x){
				if (query(i,x) & v){
					continue;
				}
				dp[x + 1] = (dp[x + 1] | cur);
			}
		}
		for (int i = a;i<=b;++i){
			if (dp[n][i])return 1;
		}
		return 0;
	};
	long long cur = 0;
	long long ans = 0;
	for (long long i = 43;i>=0;--i){
		if (check((cur ^ (1LL<<i)))){
			cur ^= (1LL<<i);
		}
		else{
			ans ^= (1LL<<i);
		}	
	}
	cout<<ans<<'\n';
	return 0;
}

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