Ducks
Description
Dengklek has ducks, numbered from to , on a number line. Initially, the -th duck starts at position and has units of energy. Every second, the following happens simultaneously to all the ducks:
- If every duck has at least one unit of energy, then each duck:
- Moves one unit to the right (increase its position by one), and
- Spends one unit of energy.
- Otherwise (at least one duck has zero energy), they all stop moving forever.
There are also seed piles, numbered from to , on the same number line. The -th seed pile is at position and weighs kilograms. When a duck arrives at a seed pile , it may eat some of the seeds. Formally, the duck will do the following:
- Eat kilograms of the seeds where . Note that must be an integer.
- The duck's energy increases by .
- The seed pile's weight decreases by .
Ducks can share seed piles (several ducks can eat from the same seed pile over time) and they coordinate their choices of how much to eat as to maximize their total moving time. Find the maximum number of seconds the ducks can continue moving under an optimal moving strategy.
Implementation Details
You should implement the following procedure.
long long max_movement(int N, int M, std::vector<int> X, std::vector<int> P, std::vector<int> Y, std::vector<int> T)
- : The number of ducks.
- : The number of seed piles.
- : arrays of integers of length describing the starting position and energy of the ducks.
- : arrays of integers of length describing the starting position and weight of the seed piles.
- This procedure should return one integer denoting the maximum number of seconds the ducks can continue moving under an optimal moving strategy.
- This procedure is called exactly once for each test case.
Constraints
- for each such that
- for each such that
- for each such that
- for each such that
- for each and such that
- for each and such that
- for each and such that and
Subtasks
Subtask |
Score |
Additional Constraints |
1 |
|
|
2 |
|
|
3 |
|
|
4 |
|
|
5 |
|
No additional constraints. |
Examples
Example 1
Consider the following call.
max_movement(3, 5, [2, 7, 9], [4, 3, 5], [3, 8, 10, 6, 1], [2, 1, 2, 3, 3])
For this example, one of the ways to maximize the number of seconds the ducks move is as follows.
- At second , the following will happen.
- Duck moves to position and eats kilogram of seeds from seed pile . Duck has units of energy. Seed pile has kilogram of seeds remaining.
- Duck moves to position and does not eat any seeds. Duck has units of energy.
- Duck moves to position and does not eat any seeds. Duck has units of energy.
- At second , the following will happen.
- Duck moves to position and does not eat any seeds. Duck has units of energy.
- Duck moves to position and does not eat any seeds. Duck has unit of energy.
- Duck moves to position and does not eat any seeds. Duck has units of energy.
- At second , the following will happen.
- Duck moves to position and does not eat any seeds. Duck has units of energy.
- Duck moves to position and eats kilogram of seeds from seed pile . Duck has units of energy. Seed pile has no seeds remaining.
- Duck moves to position and does not eat any seeds. Duck has units of energy.
- At second , the following will happen.
- Duck moves to position and eats kilogram of seeds from seed pile . Duck has units of energy. Seed pile has kilogram of seeds remaining.
- Duck moves to position and does not eat any seeds. Duck has unit of energy.
- Duck moves to position and does not eat any seeds. Duck has unit of energy.
- At second , the following will happen.
- Duck moves to position and does not eat any seeds. Duck has units of energy.
- Duck moves to position and does not eat any seeds. Duck has unit of energy.
- Duck moves to position and does not eat any seeds. Duck has unit of energy.
It can be proven that there is no eating strategy that will produce a more optimal result. Therefore, the procedure should return .
Example 2
Consider the following call.
max_movement(5, 1, [2, 3, 5, 1, 7], [6, 7, 4, 10, 2], [8], [27])
For this example, one of the ways to maximize the number of seconds the ducks move is as follows.
- At second , the following will happen.
- Duck moves to position and eats kilogram of seeds from seed pile . Seed pile has kilogram of seeds remaining. Duck now has units of energy.
- The rest of the ducks increase their position by .
- At second , the following will happen.
- Duck moves to position and eats kilogram of seeds from seed pile . Seed pile has kilogram of seeds remaining. Duck now has units of energy.
- The rest of the ducks increase their position by .
- At second , the following will happen.
- Duck moves to position and eats kilogram of seeds from seed pile . Seed pile has kilogram of seeds remaining.
- The rest of the ducks increase their position by .
- At second , the following will happen.
- Duck moves to position and eats kilogram of seeds from seed pile . Seed pile has kilogram of seeds remaining.
- The rest of the ducks increase their position by .
- At second , the following will happen.
- Duck moves to position and eats kilogram of seeds from seed pile . Seed pile has no seeds remaining.
- The rest of the ducks increase their position by .
- At second , duck , , , and will have no energy left.
It can be proven that there is no eating strategy that will produce a more optimal result. Therefore, the procedure should return .
Sample Grader
Input Format:
N M
X[0] P[0]
X[1] P[1]
⋮
X[N - 1] P[N - 1]
Y[0] T[0]
Y[1] T[1]
⋮
Y[M - 1] T[M - 1]
Output Format:
R
Here, is the integer returned by max_movement
.