Submission #920458

#	Time	Username	Problem	Language	Result	Execution time	Memory
920458		vjudge1	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	87 ms	740 KiB

sculpture

/*
 * Created: 2022-07-23 13:06
*/
#ifndef LOCAL
	#pragma GCC optimize("O3,unroll-loops")
	#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif
 
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) FOR(i,0,b)
#define FORN(i,a,b) for(int i=int(b)-1;i>=a;i--)
#define per(i,b) FORN(i,0,b)
 
#define mkp make_pair
#define pb push_back
#define ep emplace_back
#define ff first
#define ss second
#define bg begin()
#define ed end()
#define sz(x) (int)x.size()
#define all(x) (x).bg,(x).ed
#define FIO ios_base::sync_with_stdio(0);\
	cin.tie(0);
 
template<class t> using vc=vector<t>;;
template<class t> using vvc=vc<vc<t>>;
 
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vi= vc<int>;
using vll= vc<ll>;
 
 
#ifdef LOCAL
#include "/home/fuad/cp/dbg.h"
#else
#define dbg(x...)
#endif
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rngll(chrono::steady_clock::now().time_since_epoch().count());
const long long inf=1e18;
void solve() {
	int n, a, b;
	cin >> n >> a >> b;
	ll y[n];
	long long pref[n+1];
	rep(i,n)cin>>y[i];
	for(int i = 0;i<n;i++) {
		pref[i+1]=pref[i];
		pref[i+1]+=y[i];
	}
	if(a == 1) {
		ll res=(1ll<<60)-1;
		for(int B = 59;B>=0;B--) {
			res^=(1ll<<B);
			vc<ll> dp(n+1, inf);
			dp[0]=0;
			for(int i = 1;i<=n;i++) {
				for(int j = 0;j<i;j++) {
					if(((pref[i]-pref[j])|res)==res)dp[i]=min(dp[i], dp[j]+1);
				}
			}
			if(dp[n]>b){
				res^=(1ll<<B);
			}
		}
		cout<<res<<"\n";
	}
	else {
		ll res=(1ll<<60)-1;
		for(int B=59;B>=0;B--) {
			res^=(1ll<<B);
			vc<vc<ll>> dp(n+1, vc<ll>(n+1,0));
			dp[0][0]=1;
			for(int i = 1;i<=n;i++) {
				for(int j = 0;j<i;j++) {
					if(((pref[i]-pref[j])|res)==res) {
						for(int k = 1;k<=n;k++) {
							dp[i][k]|=dp[j][k-1];
						}
					}
				}
			}
			bool check=false;
			for(int i = a;i<=b;i++) {
				if(dp[n][i]==1)check=true;
			}
			if(!check)res^=(1ll<<B);
		}
		cout << res << "\n";
	}
}
 
int main () {
	FIO;
	int t=1;
	// cin >> t;
	while(t--)
		solve();
}

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