33802번 - Difference Maximization 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 181 | 82 | 75 | 55.147% |
문제
카이스트의 PS 동아리인 RUN은 무려 $N$명의 회원을 가지고 있는 유서깊은 동아리이다. 회원 수가 많은 만큼, RUN에는 매우 다양한 실력대의 회원들이 있다. RUN의 친목부장인 코코아는 회원들간의 친밀도를 조사하기 위해 회원들의 실력을 조사해두었다. 코코아는 $i$번째 회원의 실력이 양의 정수 $a_i$라는 사실과, 모든 회원들의 실력이 $M$ 이하라는 사실을 확인하였다.
코코아는 실력의 분포가 다양할수록 회원들간의 친밀도가 높을 것이라고 생각했다. 따라서, 코코아는 RUN의 친밀도를 $\sum_{1\le i<j\le n} |a_i-a_j|$와 같이 정의했다.
유감스럽게도, 업무를 처리하던 코코아는 회원들의 실력이 적힌 명부에 코코아를 쏟아 일부 회원들의 실력을 알아볼 수 없게 되었다! 코코아가 쏟아진 명부를 보면서, 문득 코코아는 알아볼 수 없게 된 회원들의 실력에 따른 RUN의 친밀도의 최댓값이 궁금해졌다. 코코아를 대신해서 실력을 알아볼 수 없는 회원들의 실력들을 $1$부터 $M$ 사이의 정수로 적절히 대체할 때, 가능한 RUN의 친밀도의 최댓값을 구해보자.
입력
첫 줄에 RUN의 회원수인 정수 $N$과, 회원들의 실력의 상계인 정수 $M$이 주어진다.
그 뒤, 두 번째 줄에 $N$개의 음이 아닌 정수 $a_i$가 공백으로 구분되어 주어진다. 이는 $a_i\ge 1$이라면 $i$번째 회원의 실력이 $a_i$라는 것이고, $a_i=0$이라면 $i$번째 회원의 실력을 알아볼 수 없다는 것이다.
출력
하나의 정수를 출력한다. 이는 $a_i=0$인 각 $i$들에 대해 해당 회원의 실력을 $1$부터 $M$사이의 정수로 적절히 대체하였을 때 얻을 수 있는 RUN의 친밀도의 최댓값이어야 한다.
제한
- $1\le N\le 100\,000$
- $1\le M\le 10^6$
- 모든 $1 \le i \le N$에 대하여 $0\le a_i\le M$
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 20 | $N\le 5, M\le 5$ |
| 2 | 20 | 모든 $1 \le i \le N$에 대하여 $a_i\ge 1$ |
| 3 | 20 | $M\le 100$ |
| 4 | 40 | 추가적인 제약 조건이 없다. |
예제 입력 1
5 5 3 0 4 0 5
예제 출력 1
22
1번, 3번, 5번 회원의 실력은 3,4,5이며, 2번, 4번 회원은 실력을 알아볼 수 없다. 친밀도가 가장 커지는 경우는 2번, 4번 회원의 실력이 각각 1,1일 때이다.
힌트
RUN에는 친목부장이라는 임원직이 실존하지 않습니다. 만약 자신을 친목부장으로 자처하는 사람을 만난다면, 즉시 다른 임원진을 호출하세요.
출처
University > KAIST > KAIST RUN Spring Contest > 2025 KAIST RUN Spring Contest B번
- 문제를 만든 사람: ibm2006
- 문제를 검수한 사람: ainta, gs22123, koosaga, leinad2, moonrabbit2, silverwolf, urd05
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호