BOBERT - Stick values

no tags 

 

 

On a sunny day, Stjepan and Bobert were arguing over their problem solving skill under a big apple tree. Bobert brought up a nice problem he had just recently solved and claimed that Stjepan could not solve it. Stjepan is desperate and needs your help. Here is Bobert's problem:

Given an array of N (1 <= N <= 10^5) numbers (0 <= ai <= 10^9) and K (1 <= K <= 20) sticks of a certain length Li (0 <= Li <= N,  such that the sum of all lengths is equal to N), find the best possible distribution of the sticks among the array such that:

 
1) a stick of length Lx can cover any interval of the array whose length is equal to the length of the stick (it can cover Lx consecutive numbers of the array)
 
2) all sticks must be used and can not overlap or leave the borders of the array 
 
3) the value of a stick of length Lx covering the interval [lo, hi] is equal to: Lx * (max[lo, hi] - min[lo, hi])
Note that: max = largest element of the array inside the interval and min = smallest element of the array inside the interval
 
4) the sum of all stick values must be as large as possible

 

Note: double-check your complexity

 

Input

 

9
2 6 3 1 8 4 3 5 6
4
2 3 2 2

The first line contains an integer N. 

The second line contains N numbers representing the array.

The third line contains an integer K.

The fourth line contains K numbers representing the stick lengths.

 

Output

The only line should contain the solution - the maximum sum of stick values as explained in the task.

Example

Input:
9
2 6 3 1 8 4 3 5 6
4
2 3 2 2

Output:
33

hide comments
nimphy: 2018-05-19 09:17:46

cost me 10s?emmm。。。。

californiagurl: 2015-06-13 13:55:43

why do i keep getting SIGABRT?

:D: 2015-03-15 00:44:21

Very fun problem. Not too hard, but pretty interesting. Thanks Vedran for preparing it.

RE: I'm glad you enjoyed it!

Last edit: 2015-04-02 09:32:08
What Does The Fox Say?: 2015-02-11 09:21:50

testcase contains Li = 0?

RE: I think some do, updated the task description, thanks!

Last edit: 2015-04-02 09:31:50
Stjepan Pozgaj: 2015-02-11 09:21:50

very nice problem!


Added by:Vedran Kurdija
Date:2015-01-08
Time limit:1s-2.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource:own problem