War for Britannia
All submissions for this problem are available.
The Field Limitary Effective Implosion Armament (F.L.E.I.J.A.) is a "Heavy Strategic Anti-strongpoint Neutralize Warhead" developed by In Vogue under the leadership of Nina Einstein. It is pronounced "Freyja", in reference to the Norse goddess of love and magic.Nina Einstein was also able to develop a countermeasure for the F.L.E.I.J.A. known as the F.L.E.I.J.A. Eliminator.
The F.L.E.I.J.A. is with Sneizel. To stop the F.L.E.I.J.A , Lelouch has to gather all his soldiers. But, due to strategical benefits, currently his soldiers are scattered. The Battle Field can be visualised as a single dimensional line. There are Ai soldiers at Point i which is located at Xi. All of them should be gathered at point X. There are bridges connecting Point i and i+1, and also between point N and X.
The width of the bridge is rather limited. The ith bridge has capacity Ci which denotes the maximum number of soldiers that can be present in any unit of the bridge at a particular time. The soldiers can travel 1 unit distance in 1 sec.They move discretely. i.e. in a particular unit time, a solider moves 1 unit or does not move at all. There are no movements for time periods not multiple of unit time. Find the minimum time in which all the soldiers can reach X. Please refer to the sample input output to get better understanding.
The first line of the input contains N denoting the number of points at which soldiers are situated. Next line contains N space separated integers Ai denoting the number of soldiers at each point.
Next line contains N space separated integers Xi denoting the location of ith point. It is guaranteed that Xi < X(i+1) and Xn < X. Next line contains N space separated integers denoting Ci the capacity of bridge between ith bridge. The Nth bridge is the one between point N and X.
Next line contains a single integer denoting location of X.
Output single integer denoting the minimum time in which all the soldiers can reach X. It is guaranteed that the output fits in a 64 bit integer.
- 1 ≤ N ≤ 105
- 1 ≤ Ci,Xi,Ai,X ≤ 109
Input 1 : 1 9 1 2 3 Input 2 : 2 16 9 1 4 8 3 9 Output 1 : 6 Output 2 : 13
Explanation for test 1
The number of soldiers at locations 1,2,3 are as follows
t =0 : (9,0,0)
t =1 : (7,2,0)
t = 2 : (5,2,2)
t = 3 : (3,2,4)
t = 4 : (1,2,6)
t = 5 : (0,1,8)
t = 6 : (0,0,9)
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, 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, LISP sbcl, LISP clisp, SCM guile, ERL, TCL, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions