Choose a monotone shortest path from house to workplace on the Manhattan grid that passes through as many errand points as possible.
Medium7Dynamic programmingSortingArrayNo attempts yetTime limit2sMemory limit512 MBAs a New Yorker you are always busy. Your workday is long, and on top of that you keep a long list of errands to run on any given day. You hate getting up early, so you always work through the list after the office, and that is eating into your free time.
One day you notice that some of the places you have to visit lie on your walk to the office, so you can stop there before work. The next day you notice that a slightly different route lets you run most of your errands without making the walk any longer. An errand takes a negligible amount of time, so you do not have to get up any earlier. This effect of the grid-like New York streets gets you thinking. Given the locations of all your errands on the New York grid, how many of them can you visit on the way to work without getting up any earlier?
The New York grid is modelled with streets parallel to the x-axis and avenues parallel to the y-axis. There is a street y=a for every integer a, and there is an avenue x=b for every integer b. An errand always takes place at an intersection of a street and an avenue. You walk to work, so you can use every road in both directions.
Several errands can take place at one intersection, and each of them is counted separately.
Print one line with the largest number of errands you can run before work on a route that is no longer than the shortest walk from your house to your workplace.