BOBERT - Stick values
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:
- 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).
- all sticks must be used and can not overlap or leave the borders of the array.
- 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.
- the sum of all stick values must be as large as possible.
Note: double-check your complexity
Input
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.
|
|
What Does The Fox Say?:
2015-02-11 09:21:50
testcase contains Li = 0?
|
|
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 |