In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of October 26th
(this exercise will still be available for submission after that deadline, but without couting towards your grade)
[to understand the context of this problem, you should read the class #03 exercise sheet]
Mary and and her friends have decided to take a trip to the Alps, where they'll be walking a beautiful mountain trail. As the trail is very long, they decided to carry their backpacks and camp for several nights along the way. For Mary, one of the best parts of the whole experience is planning the whole trip and she wants to make sure she chooses the best possible plan.
Her friends already know where it's possible to camp each night, and they also know the distance in kilometres between the possible successive camping spots. Mary's aim is to divide the route into several days in order to minimise the distance they have to walk in a single day. Imagine, for example, that they want to split the following consecutive distances into four days:
7 9 3 8 2 2 9 4 3 4 7 9 9
One possible plan would be to partition the route into the following four parts:
7 9 3 | 8 2 2 | 9 4 3 | 4 7 9 9
In this partition, they would walk 19km on the first day (7+9+3), 12km on the second day (8+2+2), 16km on the third day (9+4+3) and 29km on the last day (4+7+9+9). The "cost" of this partition would be 29km, which is the longest distance in a single day.
A better alternative would be as follows:
7 9 | 3 8 2 2 | 9 4 3 4 | 7 9 9
Now they would walk 16km, 15km, 20km and 25km each day, with the cost being 25km (the longest distance).
However, this still isn't the optimal partition for four days of travelling... Moreover, Mary would also like to know how to split the journey if she wanted three or five days instead of four. Can you help her?
Given a set of N distances, and Q queries, each indicating a number Ki of days, your task is to calculate, for each question, the optimal cost, i.e. which partition minimises the greatest distance in a single day, as explained above.
The first line of the input contains a single integer N, the number of distances to be considered. This is followed by a line with N integers Di, indicating the distances between camping sites.
The third line contains a number Q, indicating the number of queries. This is followed by Q lines, each with an integer Ki indicating the number of days Mary wishes to split the journey into.
The output should consist of Q lines, one for each question, in the same order as in the input. Each of the lines should indicate the respective optimal cost, i.e. the shortest maximum distance of a partition in Ki days of the given distances.
The following limits are guaranteed in all the test cases that will be given to your program:
| 1 ≤ N ≤ 1 000 | Quantity of distances | |
| 1 ≤ Di ≤ 1 000 | Distances | 1 ≤ Q ≤ 10 | Quantity of queries |
| 1 ≤ Ki ≤ N | Number of days in which to split the route |
| Example Input | Example Output |
13 7 9 3 8 2 2 9 4 3 4 7 9 9 3 4 3 5 |
21 27 18 |
Explanation of the example: