레이팅 미적용농부 존의 소들은 단것을 무척 좋아하고, 특히 지팡이 사탕(candy cane)을 먹는 것을 즐긴다! 농부 존에게는 총 \(N\)마리의 소가 있고 각 소는 초기 키를 가지며, 그는 소들에게 각각 높이가 다양한 \(M\)개의 지팡이 사탕을 먹이려고 한다 (\(1\le N,M\le 2\cdot 10^5\)).
농부 존은 입력에 주어진 순서대로 지팡이 사탕을 하나씩 소들에게 먹일 계획이다. 지팡이 사탕을 소들에게 먹일 때, 그는 처음에 사탕이 땅에 딱 닿도록 매달아 놓는다. 그러면 소들이 입력에 주어진 순서대로 한 마리씩 줄을 서서 사탕에 다가가, 각자 자신의 키 높이까지 사탕을 먹는다 (그보다 높은 곳에는 닿을 수 없기 때문이다). 지팡이 사탕은 처음 설치된 위치에 그대로 매달려 있으며, 소들이 사탕의 아랫부분을 먹어도 땅으로 내려오지 않는다. 사탕의 아랫부분이 이미 어떤 소의 키보다 높이 있다면, 그 소는 자기 차례에 아무것도 먹지 못할 수도 있다. 모든 소가 자기 차례를 마치면, 각 소는 자신이 먹은 사탕의 길이만큼 키가 자라고, 농부 존은 다음 지팡이 사탕을 매달아 소들이 이 과정을 다시 반복한다 (다음 사탕도 1번 소가 가장 먼저 먹기 시작한다).
문제 제공: Agastya Goel
채점 방식
- 입력 2-10: \(N, M \le 10^3\)
- 입력 11-14: 추가 제약 조건 없음.
문제 제공: Agastya Goel
첫째 줄에 \(N\)과 \(M\)이 주어진다.
다음 줄에 \(N\)마리 소의 초기 키가 주어진다. 각 값은 \([1,10^9]\) 범위이다.
다음 줄에 \(M\)개의 지팡이 사탕의 높이가 주어진다. 각 값은 \([1,10^9]\) 범위이다.
\(N\)마리 소 각각의 최종 키를 한 줄에 하나씩 출력한다.
이 문제에서 다루는 정수가 매우 클 수 있으므로 64비트 정수 자료형(예: C/C++의 "long long")이 필요할 수 있음에 유의하라.
3 2
3 2 5
6 17
2
7The first candy cane is \(6\) units tall.
- The first cow eats the portion of the first candy cane up to height \(3\), after which the remaining portion of the first candy cane occupies heights \([3,6]\).
- The second cow is not tall enough to eat any of the remaining portion of the first candy cane.
- The third cow eats two additional units of the first candy cane. The remaining portion of the first candy cane, occupying heights \([5,6]\), is not eaten.
Next, each cow grows by the amount she ate, so the heights of the cows become
\([3+3, 2+0, 5+2]=[6, 2, 7]\).
The second candy cane is \(1\) unit tall, and the first cow eats all of it.
riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > December > Bronze