Sadiq On a Date
All submissions for this problem are available.
Sadiq had planned to go on a date with his girl friend. He is also a gaming freak so he forgot about his date timings .Now, his girl friend is waiting for him and will be very angry if he doesn’t reach on time. There is timer which shows how much time he has got. As soon as the timer shows 0 , his girlfriend will go back to her hostel and Sadiq will miss his date. Also, there are n clock stations, station number i is located at point (xi,yi) on the plane. As he reaches the station i, he can increase the time on his timer by ai . But the stations are for one time use only, so if he visits some station another time ,the time won’t grow up.
Sadiq spends d.dist time units to move between stations, where dist is the distance the player has covered and d is some constant. The distance between station i and station j is determined as
Initially, sadiq is at station 1 and he has strictly more than zero and less than one unit time. Though at station 1, one unit of money can increase the time on the timer by one unit time. (Only integer units of time can be bought.)
Now Sadiq needs your help. He wants to know the minimum amount of money he needs to get to station n where his girlfriend is waiting.
The first line contains integer n and d (3<=n<=100,1000<=d<=100000) denoting the number of stations and the constant from the statement .
The second line contains n-2 integers: a2, a3,… an-1 (1<=ai<=1000).
The next n lines contain the coordinates of the stations .The ith line contains two integers xi and yi
Output the minimum amount of money in a single line.
Input: 3 1000 1000 0 0 0 1 0 3 Output: 2000
Example case 1. He will buy 2000 units of time on station1. He can't move to station 3 directly as it would cost him 3000 units of time which is more than what he has.
So he goes to station 2 which costs him 1000 units of time from staiton1.At station 2 he earns 1000 units of time totalling his time to 3000 units which is sufficient to go from station 2 to station 3.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.