29199번 - 활쏘기 대결 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 689 | 274 | 235 | 49.894% |
문제
오늘도 평화로운 KSA 수업 시간에서는 활쏘기 대결을 한다. 총 $N$개의 표적이 준비되어 있다. 표적들은 맨 위에 하나가 고정되어 있고 그 아래로 줄줄이 하나씩 매달려 있다. 표적의 번호는 $1$부터 $N$까지 매겨져 있으며, 맨 위의 표적이 $1$번이고, $i(1<i\leq N)$번 표적은 $i-1$번 표적에 매달려 있다. $i$번 표적의 점수는 $A_i$이다.
두 플레이어가 번갈아 가며 차례를 가지며, 자신의 차례가 되면 아래 두 가지 동작 중 하나를 선택해서 할 수 있다.
- 표적 하나를 선택하고 활을 쏴서 맞힌다.
- 기권한다.
표적을 활로 맞히면 표적이 파괴되며 표적의 점수가 맞힌 사람의 점수에 합산된다. 파괴된 표적 밑에 달린 표적들은 바닥에 떨어지며, 떨어졌지만 파괴되지 않은 표적들의 점수는 상대방의 점수에 합산된다. 기권할 경우, 파괴되지 않고 떨어지지도 않은 모든 표적의 점수가 상대방의 점수에 합산되고 즉시 게임이 종료된다. 모든 표적이 파괴되거나 떨어진 경우에도 게임이 종료된다. 이번에 참가할 두 학생은 엄청난 명사수라서 선택한 표적을 반드시 맞힐 수 있으며, 자신의 점수를 최대화하기 위해 최적의 선택만을 한다. 게임 결과를 예측해 보자.
입력
첫 번째 줄에 정수 $N$이 주어진다.
두 번째 줄에 각 표적의 점수를 나타내는 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다.
출력
선공이 가져갈 점수를 출력한다.
제한
- $1 \leq N \leq 2 \times 10^5$
- $-10^9 \leq A_i \leq 10^9$
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 26 | $N \leq 1000$ |
| 2 | 27 | $A_i \ge 0$ $(1 \le i \le N)$ |
| 3 | 47 | 추가 제약 조건 없음 |
예제 입력 1
3 1 10 100
예제 출력 1
101
게임은 아래와 같이 진행된다.
- 선공이 $3$번 표적을 맞히고 $100$점을 얻는다.
- 후공이 $2$번 표적을 맞히고 $10$점을 얻는다.
- 선공이 $1$번 표적을 맞히고 $1$점을 얻는다.
- 모든 표적이 파괴되거나 떨어졌으므로 게임이 종료된다.
예제 입력 2
3 1 -10 -10
예제 출력 2
1
게임은 아래와 같이 진행된다.
- 선공이 $1$번 표적을 맞히고 $1$점을 얻는다.
- $2$번과 $3$번 표적이 떨어지고 후공은 $-20$점을 얻는다.
- 모든 표적이 파괴되거나 떨어졌으므로 게임이 종료된다.
예제 입력 3
2 -3 4
예제 출력 3
1
게임은 아래와 같이 진행된다.
- 선공이 $2$번 표적을 맞히고 $4$점을 얻는다.
- 후공은 기권한다. 그 결과 선공이 $-3$점을 얻고, 게임이 즉시 종료된다.
출처
School > 한국과학영재학교 > 2023 KSA Automata Summer Contest D번
- 문제를 만든 사람: flakepowders
- 문제를 검수한 사람: ai4youej, cologne, eric00513, gs20036, jjkmk1013, jk410, juneekim7, kiwiyou, leo020630, mickeyjung, parkky, utilforever, yongwhan
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호