하타이(Hathai)는 자신의 케이터링 서비스가 동네에서 가장 신선한 음식을 제공한다는 점을 자랑스러워한다. 이를 위해 방부제가 없는 신선한 재료를 계속해서 배송받는다. 하지만 그만큼 재료가 상하지 않도록 관리하는 것이 큰 도전이 된다. 하타이의 현재 특선 메뉴는 특별히 관리해야 하는 태국 바질 잎을 정확히 \mathbf{U}장 사용한다.

하타이는 태국 바질 배송 일정표를 가지고 있다. i번째 배송은(오픈 시간으로부터 지난 분 단위의 시간인) \mathbf{M_i}의 시작 시점에 도착하며, 태국 바질 잎을 정확히 \mathbf{L_i}장 가져온다. 이 잎들은 도착한 뒤 최대 \mathbf{E_i}분 동안만 보관할 수 있다. 하타이는 특선 요리를 준비해야 하는 주문 시각 \mathbf{O_1}, \mathbf{O_2}, \dots, \mathbf{O_N}을 알고 있다. 주문 i는 시각 \mathbf{O_i}에 상하지 않은 태국 바질 잎이 \mathbf{U}장 있어야만 처리할 수 있다. 잎이 주문이 들어오는 시각에 정확히 상하게 된다면, 그 잎은 해당 주문을 처리하는 데 사용할 수 없다는 점에 유의하라. 주문을 처리하면 사용 가능한 잎들 중 \mathbf{U}장을 사용해야 하며, 사용한 잎은 이후 주문에 사용할 수 없다. 하타이가 처리할 수 없는 주문을 한 번이라도 받게 되면, 남은 모든 주문은 취소된다. 하타이는 주방을 닫고 주문 처리 일정을 어떻게 개선할지 고민해야 하기 때문이다.

예를 들어 하타이의 배송 일정이 다음 4개 배송으로 이루어져 있다고 하자:

도착 시간: 1. 수량: 10. 상하기까지 남은 시간: 2.
도착 시간: 3. 수량: 4. 상하기까지 남은 시간: 2.
도착 시간: 5. 수량: 1. 상하기까지 남은 시간: 4.
도착 시간: 10. 수량: 6. 상하기까지 남은 시간: 3.

또한 주문이 시각 3, 4, 6, 10에 총 4개 들어온다고 하자. 이 예시에서는 주문 하나를 처리할 때마다 \mathbf{U}=2장의 잎이 필요하다.

첫 번째 배송은 시각 3에 상해 버리므로, 어떤 주문에도 사용할 수 없다. 그 다음 시각 3과 4에 들어온 첫 번째/두 번째 주문은 두 번째 배송에서 온 잎 4장을 사용해 처리할 수 있다. 세 번째 주문이 들어오는 시각 6에는 보관 중인 잎이 1장뿐이므로, 하타이는 이 주문을 처리할 수 없다. 또한 시각 10에 배송이 있더라도, 하타이는 이미 주방을 닫았으므로 시각 10의 네 번째 주문 역시 처리할 수 없다. 이 예시에서 하타이가 처리한 주문의 총 개수는 2개이다.

배송 일정과 주문 일정이 주어질 때, 태국 바질 잎의 사용을 최적으로 계획하면 하타이가 처리할 수 있는 주문의 최대 개수는 얼마인가?

#10418 upload 1 done 1 how_to_reg 1

재료 최적화 timer 5s memory 1024MB

#10418

재료 최적화 5s 1024MB