29200번 - 문제 수 줄이기 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 918 | 271 | 203 | 29.335% |
문제
민찬이는 KSA 학생들을 위해 $1$번부터 $N$번까지의 문제들로 구성된 문제 목록을 준비했다. $i$번 문제의 레벨은 $A_i$이다.
학생들로부터 문제가 너무 많다는 불평을 들은 민찬이는 문제 목록을 한 개 이상의 연속된 구간으로 분할해, 구간마다 그 구간에 속한 문제들을 하나의 새로운 문제로 대체하려고 한다. 단, 각 구간에는 적어도 하나의 문제가 포함되어 있어야 하며, KSA 학생들을 더 헷갈리게 하기 위해 인접한 두 구간의 문제 수는 서로 다르도록 분할해야 한다.
새로운 문제의 레벨은 해당하는 구간에 속한 문제의 레벨을 모두 bitwise XOR한 값이다. 민찬이는 KSA 학생들의 실력 향상을 위해 새로운 문제들의 레벨 합을 최대로 하려고 한다. 문제 목록을 적절한 구간들로 분할했을 때, 새로운 문제들의 레벨 합의 최댓값을 구해보자.
입력
첫 번째 줄에 정수 $N$이 주어진다.
두 번째 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다.
출력
새로운 문제들의 레벨 합의 최댓값을 출력한다.
제한
- $1 \leq N \leq 2 \times 10^5$
- $0 \leq A_i \leq 10^9$ $(1 \leq i \leq N)$
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 23 | $N \le 100$ |
| 2 | 36 | $N \le 3000$ |
| 3 | 41 | 추가 제약 조건 없음 |
예제 입력 1
3 5 3 2
예제 출력 1
8
$[1, 2]$, $[3, 3]$ 두 구간으로 분할하면 레벨 합을 $8$로 만들 수 있다.
$(5 \oplus 3) + (2) = 8$
예제 입력 2
4 6 2 4 6
예제 출력 2
18
$[1, 1]$, $[2, 3]$, $[4, 4]$ 세 구간으로 분할하면 레벨 합을 $18$로 만들 수 있다.
$(6) + (2 \oplus 4) + (6) = 18$
예제 입력 3
4 1 2 4 8
예제 출력 3
15
$[1, 4]$ 한 구간으로 분할하면 레벨 합을 $15$로 만들 수 있다.
$(1 \oplus 2 \oplus 4 \oplus 8)= 15$
노트
음이 아닌 두 정수 $A$와 $B$의 bitwise XOR, 즉 $A \oplus B$는 다음과 같이 정의된다:
- $A \oplus B$를 이진수로 나타냈을때 $2^k$의 자리 숫자($k \geq 0$)는 $A$와 $B$에서 그 자리에 있는 숫자 중 정확히 하나가 $1$이면 $1$이고, 그렇지 않다면 $0$이다.
예를 들어, $3 \oplus 5 = 6$이다. (이진수로 나타내면: $011 \oplus 101 = 110$).
출처
School > 한국과학영재학교 > 2023 KSA Automata Summer Contest E번
- 문제를 만든 사람: mickeyjung
- 문제를 검수한 사람: ai4youej, cologne, eric00513, flakepowders, gs20036, hjroh0315, jjkmk1013, jk410, kiwiyou, leo020630, parkky, utilforever, yongwhan
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호