Bali Sculptures Batch 컴파일 명령

문제 설명

발리의 길에는 많은 조각상들이 있다. 큰길 하나에 있는 조각상들을 생각해 보자.

그 길에는 N개의 조각상들이 있고 1 부터 N까지 순서대로 번호가 붙어 있다. 조각상 i의 나이는 Yi년이다, 즉, Yi년 전에 만든 것이다. 길을 더 아름답게 만들기 위해 정부는 조각상들을 몇 개의 그룹으로 나누려고 한다. 그룹이 정해지고 나면 그룹들 사이에 아름다운 나무들을 심어서 관광객이 더 많이 오도록 만들려는 것이다.

조각상을 그룹으로 분할하는 규칙은 다음과 같다.

• 조각상들은 정확히 X개의 그룹으로 분할되어야 한다. 단, A ≤ X ≤ B이다. 각 그룹에는 최소한 하나의 조각상이 있어야 한다. 각 조각상은 단 하나의 그룹에만 속해야 한다. 각 그룹의 조각상들은 도로 상에 연속으로 존재해야 한다.
• 각 그룹에 대해서, 그룹에 속한 조각상들의 나이를 더한다.
• 그룹 별 합에 대해서, 모든 그룹 별 합의 비트 OR를 계산한다. 이 값을 분할의 아름다움 정도라고 하자.

아름다움 정도를 최소화 한다면 어떤 값이 될 것인가?

주의; 음수가 아닌 두 정수 P와 Q의 비트 OR는 다음과 같이 계산한다:

• P와 Q를 2진수로 변환.
• nP를 P의 비트 수라고 하고, nQ를 Q의 비트 수라고 하자. M은 max(nP, nQ)이다.
• P의 2진수 표현이 pM-1pM-2 .. p1p0이고 Q의 2진수 표현이 qM-1qM-2 .. q1q0라고 하자. 단, pi와 qi는 각각 P와 Q의 i번째 비트이다. 첨자 (M-1)인 비트가 가장 높은 자리수이며 첨자 0인 비트가 가장 낮은 자리수이다.
• 2진수로 P OR Q의 결과는 (pM-1 OR qM-1)(pM-2 OR qM-2)..(p1 OR q1)(p0 OR q0)이다. 단,
• • 0 OR 0 = 0
  • 0 OR 1 = 1
  • 1 OR 0 = 1
  • 1 OR 1 = 1

입력 양식

첫 줄에는 세 개의 정수 N, A, B가 주어진다. 둘째 줄에는 N개의 정수 Y1, Y2, ..., YN이 주어진다.

출력 양식

출력은 단 한 줄이며 최소로 가능한 아름다움 정도를 출력해야 한다.

입력 예

6 1 3
8 1 2 1 5 4

출력 예

11

설명

조각상들을 다음의 나이가 되도록 두 그룹으로 나눈다: (8 1 2) and (1 5 4). 그룹 별 합은 11과 10이다. 비트 OR을 계산하면 11이 된다.

부분 문제

부분 문제 1 (9점)

• 1 ≤ N ≤ 20
• 1 ≤ A ≤ B ≤ N
• 0 ≤ Yi ≤ 1,000,000,000

부분 문제 2 (16점)

• 1 ≤ N ≤ 50
• 1 ≤ A ≤ B ≤ min(20, N)
• 0 ≤ Yi ≤ 10

부 분문제 3 (21점)

• 1 ≤ N ≤ 100
• A = 1
• 1 ≤ B ≤ N
• 0 ≤ Yi ≤ 20

부분 문제 4 (25점)

• 1 ≤ N ≤ 100
• 1 ≤ A ≤ B ≤ N
• 0 ≤ Yi ≤ 1,000,000,000

부분 문제 5 (29점)

• 1 ≤ N ≤ 2,000
• A = 1
• 1 ≤ B ≤ N
• 0 ≤ Yi ≤ 1,000,000,000