All submissions for this problem are available.
Mahendra owns a water lorry and he lives in the village called Kurukshetra. The construction company in which he works is
constructing a big shopping mall in the nearby village. After he has finished the work for the day, he supplies the water
that is still remaining in the lorry to his village people. The village is subdivided into “wards”, such that each ward
has at least one house and no house can be in more than one ward. There may be houses which are haunted and doesn’t belong
to any ward. A single main road connects all the wards and the ghost houses.
Each day he will have some amount of water still left in his lorry and he will supply that to his people. But rather than stopping at every house and supplying the water, he supplies a part of the water to only one house per ward. The house resident will then divide the water among the residents of his ward. The people of the village are very selfish i.e whenever Mahendra supplies K litres of water to a house resident in a particular ward, he keeps k/2 litres for himself and divides the remaining k/2 litres among other people in his ward. So, he made a decision that each day, he would follow a different series of stoppings to supply water each day.
Moreover, Mahendra has to take care of one more problem, i.e the water tap in his lorry will loosen due to vibration and will open fully exactly after X kms of driving. So, he plans his travel accordingly in such a way that the water tap never opens fully i.e he can travel a maximum of X kms before supplying the water to the following ward. He never makes a stop to close the tap as it consumes time. So, whenever he makes a stop he will have to make the stop in such a way that he can supply water to a house. He could stop at exactly one house in each ward.
All the residents of a particular ward go on vacation for some days. Sometimes one or more wards (all houses belonging to that wards) go together. So, Mahendra doesn’t have to stop and supply water in these wards.
You will be given the starting ward number Wi and ending ward number Wj. Mahendra has to supply water to all the wards from Wi to Wj(inclusive) and wards numbered from (W0,….,Wi-1) & (Wj+1,….,Wn-1) will be on vacation. Based on the vacation list L, he will be having a list of Wi’s and Wj’s. The amount he earns from supplying water from the ward Wi to Wj is calculated as Salary=C, where ‘C’---The maximum number of days he can supply water to the wards from Wi to Wj without having to repeat any of the already followed sequence.
Sometimes, based on the given X and the house positions in the wards from Wi to Wj, Mahendra cannot supply water to all the wards from ‘Wi’ to ‘Wj’. In this case, he will not earn any money. So, he earns money only if it is possible to supply water to all the wards from ‘Wi’ to ‘Wj’. Mahendra wants to know the maximum amount of all the amounts he can earn out of the list of the given Wi’s and Wj’s.
The first line contains the number of testcases 'T'.
For each test case, the first line contains two space separated integers A and X.
A - No.of houses in the villages
X is the maximum distance the Mahendra can travel so that the water tap doesn’t open completely.
A lines will follow:
ith line will have the position of the ith house along the straight main road. (0<=Ai<=10000)
(The locations will be given in ascending order).
Next line will contain an integer M,thenumber of wards in the village.
M lines follow with each line specifying the starting and ending index of the houses located in that ward .
The next line contains ‘l’,the number of entries in vacation list ‘L’,
Then follows ‘l’ lines each containing ‘Wi’ and ‘Wj’ denoting the starting ward number and ending ward number respectively.(0<=Wi<=Wj<=M-1)
For each test case output the maximum amount the driver can earn.
Input: 1 7 3 0 1 2 3 4 5 6 3 0 1 2 4 5 6 3 0 1 1 2 0 2 Output: 8
|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, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.