1241 - Cube Tower 1
Time Limit : 2 Second
Memory Limit : 128 MB
Submission: 51
Solved: 16
- Description
- There are a large cube tower which are stacked as following:
- There are N levels, numbered 0, 1, 2, ……,N-1 from bottom to top, each has (N-i)*(N-i) cubes.
- Each level’s topmost row and leftmost column are against walls.
It is known that there is a value assigned to each cube. All cubes on the same level have a same value. You will be given the values V[i] of the cubes on each level and a number M. Find the cuboid with x*y*z cubes (1 <= x*y*z <= M , SIZE OF CUBOID CAN NOT BE 0), with the maximum total value possible. And calculate the maximum total value.
- Input
- The first line contains a single integer T, the number of test cases.
For each case:
The first line contains two integers N (1<=N<=1,000), M (1<=M<=1,000,000,000) indicating the levels and the maximum number of cubes you can get.
The second line contains N number of V[i],refer to the description (i=0,1,2,……N-1, -10000<=V[i]<=10,000).
- Output
- For each case, output a single integer, indicating the maximum total value.
- sample input
-
3 2 2 2 4 6 5 3 -2 2 1 -3 1 6 50 7 3 -2 -5 1 4
- sample output
-
6 15 252
- hint
- source
- <a href="http://www.gaewah.com/">Gaewah</a>