APIO '15 P1 - Bali Sculptures

View as PDF

Submit solution


Points: 20 (partial)
Time limit: 0.6s
Memory limit: 64M

Problem type

The province of Bali has many sculptures located on its roads. Let's focus on one of its main roads.

There are N sculptures on that main road, conveniently numbered 1 through N consecutively. The age of sculpture i is Y_i years. To make the road more beautiful, the government wants to partition the sculptures into several groups. Then, the government will plant beautiful trees between the groups, to attract more tourists to Bali.

Here is the rule in partitioning the sculptures:

  • The sculptures must be partitioned into exactly X groups, where A \le X \le B. Each group must consist of at least one sculpture. Each sculpture must belong to exactly one group. The sculptures in each group must be consecutive sculptures on the road.
  • For each group, compute the sum of the ages of the sculptures in that group.
  • Finally, compute the bitwise OR of the above sums. Let's call this the final beauty value of the partition.

What is the minimum final beauty value that the government can achieve?

Note: the bitwise OR of two non-negative integers P and Q is computed as follows:

  • Convert P and Q into binary.
  • Let nP = number of bits of P, and nQ = number of bits of Q. Let M= \max(nP, nQ).
  • Represent P in binary as p_{M-1} p_{M-2} \dots p_1 p_0 and Q in binary as q_{M-1} q_{M-2} \dots q_1 q_0, where p_i and q_i are the ith bits of p and q, respectively. The (M-1)st bits are the most significant bits, while the 0th bits are the least significant bits.
  • P \operatorname{OR} Q, in binary, is defined as (p_{M-1} \operatorname{OR} q_{M-1})(p_{M-2} \operatorname{OR} q_{M-2})\dots(p_1 \operatorname{OR} q_1)(p_0 \operatorname{OR} q_0), where
    • 0 \operatorname{OR} 0 = 0
    • 0 \operatorname{OR} 1 = 1
    • 1 \operatorname{OR} 0 = 1
    • 1 \operatorname{OR} 1 = 1

Input Specification

The first line contains three space-separated integers N, A, and B. The second line contains N space-separated integers Y_1, Y_2, \dots, Y_N.

Output Specification

A single line containing the minimum final beauty value.

Sample Input

6 1 3
8 1 2 1 5 4

Sample Output

11

Explanation of Sample Output

Partition the sculptures into 2 groups: (8\ 1\ 2) and (1\ 5\ 4). The sums are (11) and (10). The final beauty value is (11 \operatorname{OR} 10) = 11.

Subtasks

Subtask 1 (9 points)
  • 1 \le N \le 20
  • 1 \le A \le B \le N
  • 0 \le Y_i \le 1\,000\,000\,000
Subtask 2 (16 points)
  • 1 \le N \le 50
  • 1 \le A \le B \le \min(20, N)
  • 0 \le Y_i \le 10
Subtask 3 (21 points)
  • 1 \le N \le 100
  • A = 1
  • 1 \le B \le N
  • 0 \le Y_i \le 20
Subtask 4 (25 points)
  • 1 \le N \le 100
  • 1 \le A \le B \le N
  • 0 \le Y_i \le 1\,000\,000\,000
Subtask 5 (29 points)
  • 1 \le N \le 2\,000
  • A = 1
  • 1 \le B \le N
  • 0 \le Y_i \le 1\,000\,000\,000

Comments


  • 0
    account_disabled  commented on June 7, 2018, 4:40 p.m.

    Can we partition the sculptures into only one group?


    • 0
      injust  commented on June 7, 2018, 8:43 p.m.

      If A = 1, sure. But won't that always give you the maximum beauty value?