P3646 [APIO2015] Sculptures in Bali

There are many sculptures along the highways of Bali, Indonesia; we focus on one main road. There are $N$ sculptures on this road. For convenience, we number them continuously from $1$ to $N$, and the age of the $i$-th sculpture is $Y_i$ years. To make the environment of this road more beautiful, the government wants to divide these sculptures into several groups and plant some trees between groups to attract more tourists to Bali. The rules for grouping the sculptures are as follows: The sculptures must be divided into exactly $X$ groups, where $A \leq X \leq B$. Each group must contain at least one sculpture, and each sculpture must belong to exactly one group. All sculptures within the same group must occupy a contiguous segment along the road. After the sculptures are grouped, for each group we first compute the sum of ages of all sculptures in that group. Then we compute the bitwise OR of all these sums. We call this value the final aesthetic value of the grouping. What is the minimum possible final aesthetic value the government can obtain? Note: The bitwise OR of two nonnegative numbers $P$ and $Q$ is computed as follows: First convert $P$ and $Q$ to binary. Let $n_P$ be the number of binary digits of $P$, $n_Q$ be that of $Q$, and $M$ be the maximum of $n_P$ and $n_Q$. The binary representation of $P$ is $p_{M-1}p_{M-2} \dots p_1p_0$, and that of $Q$ is $q_{M-1}q_{M-2} \dots q_1 q_0$, where $p_i$ and $q_i$ are the $i$-th bits in the binary representations of $P$ and $Q$, respectively. The $(M - 1)$-th bit is the most significant bit, and the $0$-th bit is the least significant bit. The result of bitwise OR of $P$ and $Q$ is: $(p_{M-1}\mathbin{\mathrm{OR}} q_{M-1})(p_{M-2}\mathbin{\mathrm{OR}}q_{M-2})\dots (p_1\mathbin{\mathrm{OR}} q_1) (p_0\mathbin{\mathrm{OR}}q_0)$. Where: $0 \mathbin{\mathrm{OR}} 0 = 0$ $0 \mathbin{\mathrm{OR}} 1 = 1$ $1 \mathbin{\mathrm{OR}} 0 = 1$ $1 \mathbin{\mathrm{OR}} 1 = 1$.

The first line contains three integers $N, A, B$ separated by spaces. The second line contains $N$ integers $Y_1, Y_2, \dots, Y_N$ separated by spaces.

Output a single line with one number, the minimum possible final aesthetic value.

Sample Explanation: Divide the sculptures into $2$ groups, $(8, 1, 2)$ and $(1, 5, 4)$. Their sums are $(11)$ and $(10)$, and the final aesthetic value is $(11 \mathbin{\mathrm{OR}} 10) = 11$. (It is not hard to verify that this is also the minimum final aesthetic value.) Constraints: Subtask 1 (9 points) $1 \leq N \leq 20$; $1 \leq A \leq B \leq N$; $0 \leq Y_i \leq 1000000000$. Subtask 2 (16 points) $1 \leq N \leq 50$; $1 \leq A \leq B \leq \min\{20, N\}$; $0 \leq Y_i \leq 10$. Subtask 3 (21 points) $1 \leq N \leq 100$; $A = 1$; $1 \leq B \leq N$; $0 \leq Y_i \leq 20$. Subtask 4 (25 points) $1 \leq N \leq 100$; $1 \leq A \leq B \leq N$; $0 \leq Y_i \leq 1000000000$. Subtask 5 (29 points) $1 \leq N \leq 2000$; $A = 1$; $1 \leq B \leq N$; $0 \leq Y_i \leq 1000000000$. Translated by ChatGPT 5