| 컬러볼 |
|---|
지훈이가 최근에 즐기는 컴퓨터 게임이 있다. 이 게임은 여러 플레이어가 참여하며, 각 플레이어는 특정한 색과 크기를 가진 자기 공 하나를 조정하 여 게임에 참여한다. 각 플레이어의 목표는 자기 공보다 크기가 작고 색이 다른 공을 사로잡아 그 공의 크기만큼의 점수를 얻는 것이다. 그리고 다 른 공을 사로잡은 이후에도 본인의 공의 색과 크 기는 변하지 않는다. 다음 예에는 네 개의 공이 있다. 편의상 색은 숫자로 표현한다.
이 경우, 2번 공은 다른 모든 공을 사로잡을 수 있다. 반면, 1번 공은 크기가 더 큰 2번 공과 색 이 같은 3번 공은 잡을 수 없으며, 단지 4번 공만 잡을 수 있다. 공들의 색과 크기가 주어졌을 때, 각 플레이어가 사로잡을 수 있는 모든 공들의 크기의 합을 출력 하는 프로그램을 작성하시오. |
| 입력 | |
|---|---|
첫 줄에는 공의 개수를 나타내는 자연수 \(N\)이 주어진다. \((1≤n≤200,000)\). 다음 \(N\)개의 줄 중 \(i\)번째 줄에는 \(i\)번째 공의 색을 나 타내는 자연수 \(C_i\)와 그 크기를 나타내는 자연수 \(S_i\)가 주어진다. \((1 ≤ C_i ≤ N , 1 ≤ S_i ≤ 2,000)\). 서로 같은 크기 혹은 같은 색의 공들이 있을 수 있다. | |
| 출력 | |
|---|---|
\(N\)개의 줄을 출력한다. \(N\) 개의 줄 중 \(i\)번째 줄에는 \(i\)번째 공을 가진 플레이어가 잡을 수 있는 모든 공들의 크기 합을 출력한다. | |
| 예시 | |||
|---|---|---|---|
| 1 | 입력 | 4 1 10 3 15 1 3 4 8 | |
| 출력 | 8 21 0 3 | ||
| 출처 | |
|---|---|
| 2015년 한국정보올림피아드 지역 본선 고등부 2번 문제 | |