35302번 - 라면 숨기기 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 117 | 49 | 46 | 52.874% |
문제
KSA의 기숙사에서는 라면을 먹는 것이 금지되어 있다. 그러나 너무나도 배고팠던 가온이는 생활자치부의 눈을 피해 방에 $N$개의 라면을 숨기려고 한다. 각 라면은 $2, 4, \cdots, 2N$의 크기를 가진다.
가온이의 방에는 라면을 숨길 장소가 $K$개 존재한다. $i$번 장소에는 정확히 $C_i$개의 라면만을 숨길 수 있다. $(1 \le i \le K)$
이때 가온이는 가지고 있는 모든 라면을 숨겨야 하며, 각 장소에 숨길 수 있는 라면 개수의 총합은 가지고 있는 라면의 개수와 같다. 즉, $N = \sum_{i=1}^K C_i$이다.
$i$번 장소는 접근성 $A_i$를 가지며, $i$번 장소의 위험도는 다음과 같이 정의된다.
$A_i \times (i$번 장소에 숨긴 라면 크기의 중앙값$)$
단, 길이가 $n$인 수열의 중앙값은 $n$이 짝수일 때 $\cfrac{n}{2}$번째로 작은 값과 $\cfrac{n}{2}+1$번째로 작은 값의 산술평균으로, $n$이 홀수일 때 $\cfrac{n+1}{2}$번째로 작은 값으로 정의된다. 예를 들어 $[11, 16, 18, 12, 14]$의 중앙값은 $14$, $[8, 10, 18, 12, 14, 2]$의 중앙값은 $11$이다.
가온이를 도와 모든 장소의 위험도의 합을 최소화하는 방법을 찾아보자.
입력
첫 번째 줄에 두 개의 정수 $N$, $K$가 공백으로 구분되어 주어진다.
다음 $K$개의 줄 중 $i$번째 줄에 두 개의 정수 $C_i$, $A_i$가 공백으로 구분되어 주어진다.
출력
모든 장소의 위험도의 합의 최솟값을 출력한다. 주어진 조건 하에서 정답은 정수임이 보장된다.
제한
- $1 \le K \le 2 \times 10^5$
- $K \le N \le 10^9$
- $C_i \ge 1$
- $\sum_{i=1}^K C_i = N$
- $1 \le A_i \le 1000$
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 3 | $K=1$ |
| 2 | 7 | $C_i \le 2$ |
| 3 | 30 | $A_i=1$ |
| 4 | 60 | 추가 제약 조건 없음 |
예제 입력 1
5 2 4 3 1 1
예제 출력 1
23
예제 입력 2
8 3 2 3 3 5 3 4
예제 출력 2
85
출처
School > 한국과학영재학교 > 2026 KSA Automata Winter Contest H번
- 문제를 만든 사람: bennyk0406
- 문제를 검수한 사람: edward3378, eric00513, flakepowders, hjroh0315, mythofys, parkky, raehwan0418, sadtreap, utilforever, wizardrabbit
채점 및 기타 정보
- 예제는 채점하지 않는다.
- 이 문제의 채점 우선 순위는 2이다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호