29756번 - DDR 체력 관리 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 862 | 331 | 280 | 40.698% |
문제
리듬게이머 코더빡은 최근 댄스 댄스 레볼루션(DDR)에 푹 빠져있다. 이 게임은 곡이 재생될 때 떨어지는 노트에 맞춰 발판을 밟는 게임으로, 많은 체력을 소모하기 때문에 체력 관리가 매우 중요하다.
곡은 $N$개의 구간으로 이루어져 있고, 어떠한 구간 $i$ $(1 \le i \le N)$에 대해 코더빡은 해당 구간을 플레이할지, 포기할지 선택할 수 있다. 해당 구간을 플레이할 때 얻을 수 있는 점수는 $s_i$점이며, 체력을 $h_i$만큼 소모한다. 구간을 포기할 때는, 점수를 얻지 못하고 체력도 소모하지 않는다.
곡이 시작할 때, 코더빡은 체력 $100$을 가지고 시작한다. 매 구간에 진입하기 전에 체력을 $K$만큼 회복한다. 이 체력 회복은 구간을 플레이하거나 포기하는 것과는 무관하게 일어남에 유의하라. 회복 후 코더빡의 체력이 $100$을 초과하는 경우 체력이 $100$이 되며, 구간을 플레이했을 때 체력이 $0$ 미만으로 하락하는 경우 코더빡은 해당 구간을 포기해야만 한다.
하루 종일 DDR을 밟아 기진맥진인 코더빡은 더 이상 체력 관리를 위한 판단을 내릴 수 없다. 코더빡이 성과를 뽑아낼 수 있도록 그가 얻을 수 있는 최대 점수를 알려주는 프로그램을 작성하시오.
지문에서 언급하지 않은 게임오버 등의 시스템은 이 문제에서 고려하지 않는다.
입력
첫 번째 줄에는 두 정수 $N$과 $K$가 공백으로 구분되어 주어진다. $N$은 곡의 전체 구간의 수를 의미하며, $K$는 회복하는 체력의 양이다. $(1 \leq N \leq 1\,000;$ $1 \leq K \leq 10)$
두 번째 줄에는 정수 $s_1$, $s_2$, $\cdots$, $s_N$이 공백으로 구분되어 주어진다. $(1 \leq s_i \leq 1\,000)$
세 번째 줄에는 정수 $h_1$, $h_2$, $\cdots$, $h_N$이 공백으로 구분되어 주어진다. $(1 \leq h_i \leq 100)$
출력
코더빡이 얻을 수 있는 최대 점수를 출력한다.
예제 입력 1
10 10 1 2 3 4 5 6 7 8 9 10 9 9 9 9 9 9 9 9 9 9
예제 출력 1
55
모든 구간을 플레이할 수 있다.
예제 입력 2
5 10 70 90 80 100 60 60 60 60 60 60
예제 출력 2
190
세 구간 이상을 플레이하는 방법은 없다. $90$점짜리 구간을 플레이한 후 체력이 $40$이 되며, $1$개의 구간을 포기하고 체력을 $2$번 회복해 $100$점짜리 구간을 플레이하는 방법으로 최대 점수인 $190$점을 얻을 수 있다.
출처
University > 국민대학교 > 2023 국민대학교 알고리즘 콘테스트 > 2023 국민대학교 알고리즘 콘테스트 E번
University > 중앙대학교 > 중앙대학교 프로그래밍 경진대회 (CPC) > 2023 중앙대학교 프로그래밍 경진대회 (CPC) > Division 2 F번
University > 중앙대학교 > 중앙대학교 프로그래밍 경진대회 (CPC) > 2023 중앙대학교 프로그래밍 경진대회 (CPC) > Open Contest F번
University > 국민대학교 > 2023 국민대학교 알고리즘 콘테스트 > Open Contest F번