Closing ceremony
Time limit5sMemory limit512 MB
Assign every seat to a person from two entrances at (0,0) and (0,m+1), matching stamina limits to the walk distance, and say if a perfect assignment exists.
- Level
Medium6 of 10
- Topics
- Greedy, Sorting, Implementation
- Solved
- No attempts yet
Problem
The closing ceremony of Squanch Code Cup is held in a big hall with n × m seats, arranged in n rows with m seats each. Each seat has coordinates (x, y) with 1 ≤ x ≤ n and 1 ≤ y ≤ m.
Two queues of people wait to enter the hall: k people stand at (0, 0) and n·m - k people stand at (0, m + 1). Each person holds a ticket for a specific seat. If person p at (x, y) has a ticket for seat (xp, yp), that person must walk |x - xp| + |y - yp| to reach the seat.
Each person has a stamina, the maximum distance that person agrees to walk. Determine whether all n·m tickets can be distributed so that every person has enough stamina to reach their seat.
Input
The first line of input contains two integers n and m (1 ≤ n·m ≤ 104), the size of the hall.
The second line contains several integers. The first integer k (0 ≤ k ≤ n·m) is the number of people at (0, 0). The following k integers give the stamina of each person there.
The third line also contains several integers. The first integer l (l = n·m - k) is the number of people at (0, m + 1). The following l integers give the stamina of each person there.
The stamina of a person is a positive integer less than or equal to n + m.
Output
If the tickets can be distributed among the people in the described manner, print "YES"; otherwise print "NO".