| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 124 | 62 | 58 | 69.048% |
당신은 전설 속의 고대 광산을 탐험하고 있다. 이 광산 곳곳에는 값비싼 희귀 광석이 넘쳐나지만, 광석을 수집하러 들어갔다가 살아 나온 사람은 단 한 명도 없었다고 전해진다.
직접 방문한 전설의 고대 광산에는 하나의 직선 레일이 놓여 있었다. 당신은 이 레일을 따라 이동하기로 했다. 전설에서 들은 대로 광산 안에는 희귀 광석들이 넘쳐났고, 레일 옆 곳곳에는 고대의 광부들이 광석을 담아 둔 수레가 놓여 있었다. 당신은 총 $N$개의 수레에 대한 정보를 수첩에 기록해 두었다. 당신이 기록한 정보는 구체적으로 다음과 같다.
당신이 광산 입구로부터 거리가 $X$인 위치에 도달했을 때, 광산 안에서 엄청난 굉음이 들리기 시작했다. 당신은 $T$만큼의 시간이 지나면 광산 전체가 무너져 내릴 것이라는 사실을 직감했고, 근처에 있던 빈 수레를 레일에 얹은 다음 그 위에 올라탔다. 당신과 빈 수레의 질량의 합은 $M$이다. 당신은 수레를 타고 $V$의 속도로 입구를 향해 달리기 시작했다.
레일은 평평한 지형 위에 놓여 있으며 마찰이 없기 때문에, 당신이 달리는 동안 당신이 탄 수레의 운동량(질량과 속도의 곱)은 $MV$로 일정하게 유지될 것이다. 이 속도라면 탈출에 성공할 수 있을 거라는 확신에 찬 당신은, 조금 더 욕심을 내서 달리는 도중 만나는 수레에 담긴 광석 주머니 몇 개를 담아 가기로 결심했다. 당신은 손이 빠르기 때문에 순식간에 옆 수레에서 광석 주머니를 가져올 수 있다. 하지만 주머니를 담을 때마다 당신이 탄 수레는 무거워지고, 운동량 보존의 법칙에 의해 당신이 탄 수레는 느려지게 된다. 구체적으로, 당신이 주머니를 담은 이후의 질량을 $M',ドル 그 때의 속도를 $V'$라고 하면, $M'V' = MV$가 성립한다.
당신의 최우선 목표는 전설의 고대 광산을 살아 나오는 것이다. 시간 $T$ 이내에 광산 입구에 도달해야 하며, 정확히 $T$만큼의 시간이 걸려도 괜찮다. 또한 당신은 수레에 담은 광석의 총가치도 최대화하고자 한다. 당신이 전설의 고대 광산을 살아 나오는 것이 가능하다면, 가지고 나올 수 있는 광석의 총가치는 최대 얼마일지 계산하시오.
첫 번째 줄에 $X, T, M, V, N$이 공백으로 구분되어 주어진다.
두 번째 줄부터 $N$개의 줄만큼 $x_i, m_i, c_i$가 공백으로 구분되어 주어진다.
당신이 전설의 고대 광산을 탈출하는 것이 가능하다면, 당신이 가지고 나올 수 있는 광석의 총가치가 최대 얼마인지 출력한다.
당신이 전설의 고대 광산을 탈출하는 것이 불가능하다면, $-1$을 출력한다.
5 5 5 5 3 5 10 3 5 10 7 5 10 2
10
5 2 5 2 3 5 10 3 5 10 7 5 10 2
-1
Contest > BOJ User Contest > Good Bye, BOJ > Good Bye, BOJ 2022! F번