22876번 - 츠바메가에시 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 463 | 197 | 149 | 41.737% |
문제
"츠바메가에시"(つばめがえし)는 일본의 검사 "사사키 코지로"가 날아가는 제비를 베었다고 전해지는 검 초식의 이름이다. 기록상으로는 세 번 연속 칼질을 했다고 전해지나, 실제로 기술을 재연해 본 바에 따르면 두 번 연속 까지가 한계라고 한다. 하지만 세 번 연속 베는 것이 더 멋있어 보이므로 게임이나 애니메이션 등의 미디어에서 이 기술을 묘사할 때는 검격을 세 번 하는 모습을 주로 볼 수 있다.
미디어에 영향을 많이 받은 pichulia는 세 번 연속 베는 기술을 재연하고자 한다. 피나는 노력 끝에 pichulia는 마침내 X 축 또는 Y 축과 평행한 무한한 길이의 직선 형태의 검격을 구사할 수 있게 되었다.
연습은 끝났고 이제는 실전이다. 하지만 pichulia는 야생생물 보호 및 관리에 관한 법률 제19조 1항에 의거해 야생의 제비를 벨 수 없었고, 부득이하게 제비뽑기의 제비를 베기로 결심했다.
2차원 평면상에 $N$개의 제비가 있고, 각 제비마다 베었을 때 얻을 수 있는 점수를 가지고 있다. 정확히 세 번의 검격을 통해 얻을 수 있는 점수의 최댓값을 구해보자.
점수는 검격들에 베인 제비의 점수들의 합이다. 단, 한 제비를 여러 번 베어도 점수는 한 번만 더해진다.
| 그림 D.1: 2차원 평면상에 배치된 제비 | 그림 D.2: 세 번의 검격으로 제비를 베는 모습 |
입력
첫 번째 줄에는 제비의 개수 $N$($ 1 \leq N \leq 300\ 000 $)이 주어진다.
두 번째 줄부터 $N+1$번째 줄까지 $N$줄에 걸쳐서 세 정수 $x$, $y$, $v$가 공백으로 구분되어 주어진다. 이는 2차원 평면상의 좌표 ($x$, $y$) 에 점수가 $v$ 인 제비가 있음을 의미한다. ($0 \leq x, y \leq 1\ 000\ 000$, $1 \leq v \leq 7\ 000$)
모든 제비의 위치는 서로 다르다.
출력
정확히 세 번의 검격을 통해 얻을 수 있는 점수의 최댓값을 출력한다.
예제 입력 1
10 1 1 8 1 4 1 1 5 9 2 3 2 2 4 1 3 1 9 3 2 9 3 4 4 4 3 3 5 4 7
예제 출력 1
48
예제 입력 2
8 1 0 1 1 1000000 1 2 1 1 2 999999 1 3 2 1 3 999998 1 4 3 1 4 999997 1
예제 출력 2
6
예제 입력 3
1 1 1 3
예제 출력 3
3
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호