시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 253 | 81 | 63 | 29.167% |
영민이는 수많은 프로젝트로 너무 피곤한 나머지 금방이라도 잠들어버릴 것 같은 상태이다. 그래서 에너지 드링크의 힘을 빌려 지금부터 최대한 오래 깨어 있고자 한다. 에너지 드링크를 마시면 금방 졸음이 달아나 일정 시간만큼 깨어 있는 상태로 버틸 수 있지만, 몸 안에 카페인이 축적된 만큼 에너지 드링크의 효과 지속 시간이 줄어든다. 따라서 어느 시점부터는 에너지 드링크를 마셔도 아무 효과가 없는 상태에 이른다.
영민이는 $N$개의 에너지 드링크를 가지고 있다. $i$번째 에너지 드링크는 고유 에너지 값 $E_i$ 와 고유 카페인 값 $C_i$를 가진다. 에너지 드링크 하나를 마시면, 이전까지 몸에 축적된 카페인의 총량을 $S$라고 할 때, 효과가 $\max\left(0,E_i - S\right)$ 초 지속되고, 몸에 카페인이 $C_i$만큼 축적된다. 단, 처음 몸에 축적된 카페인의 총량은 $0$이며, 카페인을 배출하는 일은 일어나지 않는다.
에너지 드링크를 마시는 데에는 $1$초가 걸리고, 효과는 에너지 드링크를 마신 직후부터 시작된다. 영민이는 당장 에너지 드링크 하나를 마실 수 있으며, 하나도 마시지 않을 경우 바로 잠들게 된다. 단, 에너지 드링크는 $1$초에 하나씩만 마실 수 있다.
각 에너지 드링크에 대한 정보가 주어질 때, 영민이가 지금부터 얼마나 오랫동안 깨어 있을 수 있는지 출력하는 프로그램을 작성하시오.
첫 번째 줄에는 $N$이 주어진다. $\left(1 \le N \le 5\,000 \right)$
두 번째 줄에는 $N$개의 정수가 공백으로 구분되어 주어진다. $i$번째 수는 $E_i$이다. $(0 \le E_i \le 1\,000\,000)$
세 번째 줄에는 $N$개의 정수가 공백으로 구분되어 주어진다. $i$번째 수는 $C_i$이다. $(0 \le C_i \le 1\,000\,000)$
영민이가 지금부터 깨어 있을 수 있는 최대 시간을 출력한다. 시간의 단위는 초이다.
5 10 20 30 40 50 50 40 30 20 10
80
5 10 30 60 90 200 10 20 30 40 50
250
2 0 0 10 20
0
1 5 5
5
에너지 드링크의 효과 지속 시간은 이전의 효과 지속 시간에 더해지는 것이 아니라 에너지 드링크를 마신 직후부터 시작되는 것임에 유의하자. 즉, 두 에너지 드링크의 효과 지속 시간이 겹칠 수 있다.
University > 한양대학교 > 제8회 한양대학교 프로그래밍 경시대회 > Beginner Division F번
University > 한양대학교 > 제8회 한양대학교 프로그래밍 경시대회 > Advanced Division F번