Criss-Cross Cables
Time limit2.5sMemory limit512 MB
Place m edges between n fixed points on a line with given lengths, reusing ports but with no repeated pair; say whether all m wires fit.
- Level
Medium7 of 10
- Topics
- Greedy, Sorting, Math, Implementation
- Solved
- No attempts yet
Problem
As a participant in the BAPC (Bizarrely Awful Parties Competition) you are preparing for your next show. You do not know anything about music, so you rip off someone else's playlist and decide not to worry about that any more. What you do worry about is the aesthetics of your set-up: if it looks too simple, people will be unimpressed and they might figure out that you are actually a worthless DJ.
It does not take you long to come up with a correct and fast solution to this problem. You add a long strip with a couple of useless ports, and add some useless cables between these ports. Each of these cables connects two ports, and these special ports can be used more than once. Everyone looking at the massive tangle of wires will surely be in awe of your awesome DJ skills.
However, you do not want to connect the same two ports twice directly. If someone notices this, then they will immediately see that you are a fraud!
You have made a large strip, with the ports in certain fixed places, and you have found a set of cables with certain lengths that you find aesthetically pleasing. When you start trying to connect the cables, you run into another problem. If the cables are too short, you cannot use them to connect the ports! So you ask yourself the question whether you are able to fit all of the cords onto the strip or not. If not, the aesthetics are ruined, and you will have to start all over again.
Input
- The first line has , the number of ports on the strip, and , the number of wires, with and .
- The second line has integers , the positions of the sockets, with .
- The third line has integers , the lengths of the wires, with .
Output
Print yes if it is possible to plug in all the wires, or no if this is not possible.