1369 - Group II
Time Limit : 2 Second
Memory Limit : 128 MB
Submission: 84
Solved: 3
- Description
- There is a sequence of N numbers. Cut them into not more than K groups without changing their order, and each group must consist of at least L numbers. From left to right, the value of the i-th group is the sum of all numbers in the group multiplying i. Give me the minimum sum of all the values.
- Input
- The first line is a number T indicating the total number of test cases. (T<=20)
Then T cases, for each case:
First line is three numbers N, K, L which are descripted above.(1<=N<=2000000, 1<=L,K<=100)
Then N numbers ranged in [-1000, 1000].
Huge input datas, scanf or getchar is recommand. - Output
- For each case, output the minimum sum in a line.
- sample input
-
2 5 3 1 3 -2 -1 -4 5 5 3 2 3 -2 -1 -4 5
- sample output
-
-1 1
- hint
- To get the best answer you can try: Case 1: (3)(-2 -1 -4 5) or (3)(-2)(-1 -4 -5) Case 2: (3 -2)(-1 -4 5)
- source
- Hust Monthly 10.06.13/Zehua HONG