|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|5 초||256 MB||3||0||0||0.000%|
Tourists in the numerous Welsh valleys are in need of an IT solution to their transportation troubles. They want to see all the local Points of interest (POIs) in a specific order already set out by their trusty tour guides.
Visitors have to rely on various types of transportation: car, rickshaw, donkey cart, etc. These are only available on call, which is unfortunate as the poor mobile reception in the depths of the idyllic valleys means transportation type can only change at a POI.
Further, a driver will only offer tourists transportation between points pi, pi+1, . . . , pj−1, pj under the following conditions:
What the tourists want is a transportation switching scheme, which is a list of increasing indices s0 . . . sk where points psi are the locations to switch the type of transportation (the same transportation type can be used more than once, but another instance of the same type will need to be hailed once the original driver has had enough).
Write one line containing one number k: the minimal number of times we have to call for a new type of transportation to visit all n points in the given order, if this is possible. If not, output IMPOSSIBLE.
4 4 100 30000 200 20000 300 10000 400 0 50 10000 75 20000 400 -40000
1 3 20 50000 100 10000 10 -60000