33719번 - [I] I'm GM! 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 68 | 53 | 37 | 88.095% |
문제
다들 알고 있다시피, hibye1217은 포드코스에서 Grandmaster의 등급을 가지고 있다. 이를 기념할 겸 과거를 돌아보던 hibye1217은 문득 아래와 같은 궁금증을 가지게 되었다.
'만약 일부 대회를 계산에서 제외할 수 있다면 얼마나 더 높은 레이팅을 받을 수 있을까?'
포드코스의 레이팅의 계산 방식은 다음과 같다.
- 유저의 레이팅은 $0$에서 시작한다.
- 포드코스의 각 대회에는 레이팅 상수라는 두 정수 $a$, $b$가 존재한다. 이는 각 대회가 유저의 레이팅에 얼마나 큰 영향을 끼치는지를 의미한다. 레이팅 상수는 대회마다 다를 수 있다.
- 유저가 대회를 치기 전의 레이팅이 정수 $r$이었고, 대회에서의 퍼포먼스가 정수 $p$였다고 하자. 그러면 유저의 새로운 레이팅은 $\displaystyle \frac{ap+br}{a+b}$이 된다.
- 만약 새로운 레이팅이 정수가 아니라면, 소수점 아랫부분이 $0.5$ 미만이라면 내림하고 $0.5$ 이상이라면 올림한다.
포드코스의 Grandmaster인 hibye1217은 $N$개의 대회 중 $0$개 이상의 대회를 계산에서 제외하는 경우의 수는 $2^N$가지 경우나 있으니 쉽게 풀 수 없다는 결론을 냈다. 이제 포드코스의 Legendary Grandmaster인 여러분들이 이 문제를 효율적으로 풀어 보자!
일부 대회를 계산에서 제외할 수는 있어도 대회 간의 순서를 바꿀 수는 없음에 유의하라.
입력
첫째 줄에는 hibye1217이 참여한 대회의 개수 $N$이 주어진다. $(1 \le N \le 500\,000)$
둘째 줄부터 $N$개의 줄에 걸쳐, $i+1$번째 줄에는 hibye1217이 참여한 $i$번째 대회의 레이팅 상수인 두 정수 $a$, $b$와 대회에서의 퍼포먼스인 정수 $p$가 공백으로 구분되어 주어진다. $(1 \le a, b \le 1\,000; 0 \le p \le 4\,000)$
출력
첫째 줄에 일부 대회를 계산에서 제외할 수 있을 때 hibye1217이 받을 수 있는 레이팅의 최댓값을 출력한다.
예제 입력 1
4 1 2 1729 7 1 3621 2 1 2496 3 5 2146
예제 출력 1
3240
$4$개의 대회가 모두 계산에 들어간다면 레이팅이 $2\,520$밖에 되지 않지만, $3$번째 대회와 $4$번째 대회를 제외하고 계산하면 레이팅이 $3\,240$이 된다.
출처
- 문제를 만든 사람: hibye1217
- 문제를 검수한 사람: minjunnick, mujigae, nflight11, oh040411, utilforever
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호