시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
1.0 초 64 MB 3 3 (100%) 3
문제
시간 제한 1초, 메모리 제한 64MB 발리 지방의 도로 위에는 여러 조각상들이 있다. 그 중 하나의 도로에만 집중해보자. 그 도로에는 $N$개의 조각상이 있고 편의상 $1$부터 $N$까지 순차적으로 번호를 매긴다고 하자. $i$번 조각상의 나이는 $Y_i$로 표현한다. 도로를 더 아름답게 만들기 위해서 정부는 조각상들을 몇 개의 그룹으로 나누고자 한다. 그리고 정부는 그 그룹들 사이에 아름다운 나무를 심어서 더 많은 여행자들을 발리에 모으고자 한다. 조각상의 분할에 대한 규칙은 아래와 같다. - 조각상은 정확하게 $X$개의 그룹으로 나누어져야 하고 $A ≤ X ≤ B$를 만족시켜야 한다. 각 그룹은 적어도 하나의 조각상을 포함해야 하며 각 조각상은 정확하게 하나의 그룹에만 포함되어야 한다. 그리고 같은 그룹 안에 속하는 조각상들은 도로상에서 연속적인 위치에 있어야 한다. - 각 조각상 그룹에 대해서 속해있는 조각상들의 나이의 합을 계산한다. - 마지막으로 그 합들에 bitwise OR 연산을 수행한다. 이 값을 해당 분할의 최종 아름다움 점수로 부르자. 정부가 얻을 수 있는 최종 아름다움 점수의 최소값을 구하라. 참고: 두 음이 아닌 정수 $P, Q$에 대한 bitwise OR 연산은 아래와 같다. - $P, Q$를 이진수로 변환한다. - $nP = P$의 비트수, $nQ = Q$의 비트수라 하고 $M = max(nP, nQ)$라 하자. - $P$를 이진수로 $p_{M-1}p_{M-2}..p_1p_0$이라 하고 $Q$를 이진수로 $q_{M-1}q_{M-2}..q_1q_0$라 표현하자($p_i, q_i$는 $P, Q$의 $i$번째 비트.) $M-1$번째 비트가 가장 높은 자리수이고 $0$번 비트가 가장 낮은 자리수(일의 자리수)이다. - 이진수의 $P$ OR $Q$는 ($p_{M-1}$ OR $q_{M-1}$)($p_{M-2}$ OR $q_{M-2}$)..($p_1$ OR $q_1$)($p_0$ OR $q_0$)으로 정의되고 여기서의 OR는 아래와 같다. - 0 OR 0 = 0 - 0 OR 1 = 1 - 1 OR 0 = 1 - 1 OR 1 = 1
입력
첫째 줄에 띄어쓰기로 구분된 세 개의 정수 $N, A, B$가 주어진다. 둘째 줄에는 띄어쓰기로 구분된 $N$개의 정수 $Y_1, Y_2, ..., Y_N$이 주어진다.
출력
최종 아름다움 정수를 한 줄에 출력하라.
힌트
#### 예제 입력 ``` 6 1 3 8 1 2 1 5 4 ``` #### 예제 출력 ``` 11 ``` #### 설명 조각상의 분할은 두 개의 그룹으로 이루어진다: (8 1 2)와 (1 5 4). 합은 각각 11과 10이고 최종 아름다움 점수는 (11 OR 10) = 11이다. #### 서브태스크 - 서브태스크 1 (9점) - $1 ≤ N ≤ 20$ - $1 ≤ A ≤ B ≤ N$ - $0 ≤ Y_i ≤ 1,000,000,000$ - 서브태스크 2 (16점) - $1 ≤ N ≤ 50$ - $1 ≤ A ≤ B ≤ min(20, N)$ - $0 ≤ Y_i ≤ 10$ - 서브태스크 3 (21점) - $1 ≤ N ≤ 100$ - $A = 1$ - $1 ≤ B ≤ N$ - $0 ≤ Y_i ≤ 20$ - 서브태스크 4 (25점) - $1 ≤ N ≤ 100$ - $1 ≤ A ≤ B ≤ N$ - $0 ≤ Y_i ≤ 1,000,000,000$ - 서브태스크 5 (29점) - $1 ≤ N ≤ 2,000$ - $A = 1$ - $1 ≤ B ≤ N$ - $0 ≤ Y_i ≤ 1,000,000,000$