Ducks

Description

Dengklek has N ducks, numbered from 0 to N1, on a number line. Initially, the i-th duck starts at position X[i] and has P[i] 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:
    1. Moves one unit to the right (increase its position by one), and
    2. Spends one unit of energy.
  • Otherwise (at least one duck has zero energy), they all stop moving forever.

There are also M seed piles, numbered from 0 to M1, on the same number line. The j-th seed pile is at position Y[j] and weighs T[j] kilograms. When a duck arrives at a seed pile j, it may eat some of the seeds. Formally, the duck will do the following:

  • Eat x kilograms of the seeds where 0xcurrent weight of seeds. Note that x must be an integer.
  • The duck's energy increases by x.
  • The seed pile's weight decreases by x.

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)
  • N: The number of ducks.
  • M: The number of seed piles.
  • X,P: arrays of integers of length N describing the starting position and energy of the ducks.
  • Y,T: arrays of integers of length M 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

  • 1N100000
  • 1M100000
  • 0X[i]109 for each i such that 0i<N
  • 0P[i]109 for each i such that 0i<N
  • 0Y[j]109 for each j such that 0j<M
  • 0T[j]109 for each j such that 0j<M
  • X[i]X[j] for each i and j such that 0i<j<N
  • Y[i]Y[j] for each i and j such that 0i<j<M
  • X[i]Y[j] for each i and j such that 0i<N and 0j<M

Subtasks

Subtask Score Additional Constraints
1 9 N=1
2 12 M=1
3 26 N1000;M1000
4 34 N50000;M50000
5 19 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.

  1. At second 1, the following will happen.
    • Duck 0 moves to position 3 and eats 1 kilogram of seeds from seed pile 0. Duck 0 has 4 units of energy. Seed pile 0 has 1 kilogram of seeds remaining.
    • Duck 1 moves to position 8 and does not eat any seeds. Duck 1 has 2 units of energy.
    • Duck 2 moves to position 10 and does not eat any seeds. Duck 2 has 4 units of energy.
  2. At second 2, the following will happen.
    • Duck 0 moves to position 4 and does not eat any seeds. Duck 0 has 3 units of energy.
    • Duck 1 moves to position 9 and does not eat any seeds. Duck 1 has 1 unit of energy.
    • Duck 2 moves to position 11 and does not eat any seeds. Duck 2 has 3 units of energy.
  3. At second 3, the following will happen.
    • Duck 0 moves to position 5 and does not eat any seeds. Duck 0 has 2 units of energy.
    • Duck 1 moves to position 10 and eats 2 kilogram of seeds from seed pile 2. Duck 1 has 2 units of energy. Seed pile 2 has no seeds remaining.
    • Duck 2 moves to position 12 and does not eat any seeds. Duck 2 has 2 units of energy.
  4. At second 4, the following will happen.
    • Duck 0 moves to position 6 and eats 2 kilogram of seeds from seed pile 3. Duck 0 has 3 units of energy. Seed pile 3 has 1 kilogram of seeds remaining.
    • Duck 1 moves to position 11 and does not eat any seeds. Duck 1 has 1 unit of energy.
    • Duck 2 moves to position 13 and does not eat any seeds. Duck 2 has 1 unit of energy.
  5. At second 5, the following will happen.
    • Duck 0 moves to position 7 and does not eat any seeds. Duck 0 has 2 units of energy.
    • Duck 1 moves to position 12 and does not eat any seeds. Duck 1 has 0 unit of energy.
    • Duck 2 moves to position 14 and does not eat any seeds. Duck 2 has 0 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 5.

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.

  1. At second 1, the following will happen.
    • Duck 4 moves to position 8 and eats 10 kilogram of seeds from seed pile 0. Seed pile 0 has 17 kilogram of seeds remaining. Duck 4 now has 11 units of energy.
    • The rest of the ducks increase their position by 1.
  2. At second 3, the following will happen.
    • Duck 2 moves to position 8 and eats 7 kilogram of seeds from seed pile 0. Seed pile 0 has 10 kilogram of seeds remaining. Duck 2 now has 8 units of energy.
    • The rest of the ducks increase their position by 1.
  3. At second 5, the following will happen.
    • Duck 1 moves to position 8 and eats 4 kilogram of seeds from seed pile 0. Seed pile 0 has 6 kilogram of seeds remaining.
    • The rest of the ducks increase their position by 1.
  4. At second 6, the following will happen.
    • Duck 0 moves to position 8 and eats 5 kilogram of seeds from seed pile 0. Seed pile 0 has 1 kilogram of seeds remaining.
    • The rest of the ducks increase their position by 1.
  5. At second 7, the following will happen.
    • Duck 3 moves to position 8 and eats 1 kilogram of seeds from seed pile 0. Seed pile 0 has no seeds remaining.
    • The rest of the ducks increase their position by 1.
  6. At second 11, duck 0, 1, 2, and 3 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 11.

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, R is the integer returned by max_movement.


Time Limit: 8 Seconds
Memory Limit: 1024MB
Your best score: 0
Source: SEATST 2025 (Day 2)

Subtask Score
1 9
2 12
3 26
4 34
5 19
6 0