Want to try solving this problem? You can submit your code online if you log in or register.
After her foiled attempt to steal the Eiffel Tower, Carmen Sanfrancisco is back, and this time the villainess plans to `rob' several high-profile banks. (The whole banks! You get it? She's gonna steal actual entire buildings!) Fortunately, the ACME Detective Agency is well aware of this plot and has requested your services as an elite detective to track down Carmen's current whereabouts.
You have obtained a map of all the cities in which Carmen Sanfrancisco could currently be hiding. These cities are arranged in a line along a single highway, and it takes an hour to travel from any city to the city directly east or west of it. You know which cities have a bank Carmen is interested in stealing, and you know that once in a city, Carmen takes practically no time to steal a bank (she is a well-prepared master criminal after all).
When Carmen starts moving, the highway patrols will mobilise to close the roads between every city. You know how many hours it will take for the highway patrol to close the road between any pair of adjacent cities, and so does Carmen. Since Carmen won't compromise on the banks she intends to steal, her starting point must be in a city where it's possible for her to reach all the banks before the roads close. Your task is to determine from how many different cities Carmen could begin her heist.
Each city is assigned a unique number from 1 to N, numbered from west to east.
The next line of input contains C integers, in ascending order. These are the cities with a bank.
The final line of input contains N - 1 integers, the ith of these ti, representing how many hours it takes to close the road between city i and city i + 1.
6 3 3 5 6 3 2 2 5 9
For all subtasks, 1 <= N <= 100,000, 1 <= C <= N, and 0 <= ti < 1,000,000.
© Australian Mathematics Trust 2001-2023
Page generated: 25 March 2023, 6:29pm AEDT