| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 554660 | kwongweng | Bali Sculptures (APIO15_sculpture) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
Solution for APIO 2015 - Bali Sculpture
Tags :
*/
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define fi first
#define se second
ll MOD = 1000000007;
ll power(ll base, ll n){
if (n == 0) return 1;
if (n == 1) return base;
ll halfn = power(base, n/2);
if (n % 2 == 0) return (halfn * halfn) % MOD;
return (((halfn * halfn) % MOD) * base) % MOD;
}
ll inverse(ll n){
return power(n, MOD-2);
}
ll add(ll a, ll b){
return (a+b) % MOD;
}
ll mul(ll a, ll b){
a %= MOD;
return (a*b) % MOD;
}
ll gcd(ll a, ll b){
if (a == 1) return 1;
if (a == 0) return b;
return gcd(b%a, a);
}
void solve(){
int n, a, b; cin >> n >> a >> b;
vi y(n+1); FOR(i,1,n+1) cin >> y[i];
vi p(n+1); FOR(i,1,n+1) p[i] = p[i-1] + y[i];
if (n<=20){
//bitmask, O(n * 2^n)
ll ans = MOD*MOD;
ll ans = MOD*MOD;
FOR(mask,0,(1<<(n-1))){
ll val = 0; int cnt = 0; int cur = 0;
FOR(i,0,n-1){
if (mask&(1<<i)){
cnt++;
val |= (p[i+1]-p[cur]);
cur = i+1;
}
}
cnt++; val |= (p[n]-p[cur]);
if (a <= cnt && cnt <= b) ans = min(ans, val);
}
cout << ans << '\n';
return;
}
// knapsack O(n^3 * b * max(y[i]))
int ans = MOD;
int max_a = n * 20 + 1;
int dp[n+1][b+1][max_a];
ms(dp,-1,sizeof(dp));
FOR(i,1,n+1){
dp[i][1][p[i]-p[0]] = 1;
}
FOR(j,2,b+1){
FOR(i,2,n+1){
FOR(k,1,i){
int val = p[i]-p[k];
FOR(l,0,max_a){
if (dp[k][j-1][l] != -1){
int new_val = l|val;
dp[i][j][new_val] = 1;
}
}
}
}
}
FOR(l,0,max_a){
bool sol = false;
FOR(j,a,b+1){
if (dp[n][j][l] == 1){
cout<<l; sol = true;
break;
}
}
if (sol) break;
}
}
int main() {
ios::sync_with_stdio(false);
int TC = 1;
//cin >> TC;
FOR(i, 1, TC+1){
//cout << "Case #" << i << ": ";
solve();
}
}