시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 12 | 9 | 8 | 72.727% |
Hathai is proud that her catering service provides the freshest food in town. To accomplish that, she gets fresh ingredients with no preservatives delivered constantly. This brings about the challenge of preventing the ingredients from spoiling. Her current special uses exactly $U$ leaves of Thai basil, that need special care.
Hathai has the schedule of the deliveries of Thai basil. The $i$-th delivery comes at the beginning of time $M_i$ (in minutes since opening time), and brings exactly $L_i$ leaves of Thai basil that can be stored for at most $E_i$ minutes since arriving. Hathai has orders to prepare her specialty dish at times $O_1,O_2, \dots ,O_N$. Order $i$ can only be fulfilled if she has $U$ unspoiled leaves of Thai basil at time $O_i$. Note that if leaves would spoil at the same time an order comes in, those leaves cannot be used to fulfill that order. If an order is fulfilled, $U$ of the leaves available have to be used and cannot be used for future orders. Once Hathai gets an order that she cannot fulfill, all of the remaining orders will also be canceled because she needs to close her kitchen and think about how to improve the fulfillment schedule.
For example, suppose Hathai's schedule has the following $4$ deliveries:
And also suppose she has $4$ orders placed at times $3$, $4$, $6$ and $10$. Each order requires using $U=2$ leaves in this example.
The first delivery become spoiled at time $3$, so it cannot be used on any order. Then the first order and the second order at time $3$ and time $4$ can be fulfilled and use up the $4$ leaves from the second delivery. For the third order at time $6$, there is only $1$ leaf in the storage, so Hathai cannot fulfill this order. Note that although there is a delivery at time $10$, she still cannot fulfill the fourth order at time $10$ because she has already closed her kitchen. In this example, Hathai managed to fulfill $2$ orders in total.
Given the delivery and order schedules, find out the maximum number of orders Hathai can fulfill if she optimizes the use of the Thai basil leaves.
The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case starts with a line containing three integers $D$, $N$, and $U$: the number of deliveries, the number of orders and the amount of leaves needed for each order, respectively. Then, $D$ lines follow. The $i$-th of these lines contains three integers $M_i$, $L_i$, and $E_i$: the time of the delivery in minutes since opening time, the amount of Thai basil leaves delivered, and the number of minutes those leaves can be stored and remain fresh, respectively, of the $i$-th delivery. Then, the last line contains $N$ integers $O_1,O_2, \dots ,O_N$, where $O_j$ is the time, in minutes since opening time, at which the $j$-th order must be prepared.
For each test case, output one line containing Case #x: y
, where $x$ is the test case number (starting from 1) and $y$ is an integer representing the maximum number of orders Hathai can fulfill.
2 2 4 5 20 8 1000000000 60 4 1000000000 10 30 50 70 3 5 5 20 8 1000000000 50 3 1000000000 60 100 1000000000 30 50 59 70 90
Case #1: 0 Case #2: 2
In Sample Case #1, Hathai cannot fulfill the first order, because it came too early, before any deliveries brought in Thai leaves. So she has to close her kitchen immediately without fulfilling any order.
In Sample Case #2, Hathai can fulfill the first order, and her second delivery arrives just in time to help her fulfill the second order. However, the huge third delivery does not get to her in time to help her with the third order, so that one goes unfulfilled and so do the remaining ones.
1 4 4 2 1 10 2 3 4 2 5 1 4 10 6 3 3 4 6 10
Case #1: 2
This additional sample is the one explained in the problem statement.
Contest > Google > Code Jam to I/O for Women > Code Jam to I/O for Women 2022 > Code Jam to I/O for Women 2022 B번