Makx SumProblem code: KSUBSUM |
All submissions for this problem are available.
Did you know that the Hindus believe there are 330 million deities ? Lets discuss about them in long contests. The three main forces of god Brahma, Vishnu and Mahesh, also called Trimurti ( 3 forms ), want to decide when to end the world. Given an array A, which contains the 'Good' ( or 'Evil' ) score of each place on earth, they can easily find the maximum sum of the scores of a (contiguous) sub-array of places. But this is not much useful to them. So, each of them gives a value K and want to know the Kth maximum sum of scores of a contiguous sub-array. In other words, find the value of S[K] (1-based index), where the array S contains the sums of all possible contiguous sub-arrays in non-increasing order.
Input
First line contains T, number of test cases. T cases follow. In each test case, first line contains N K1 K2 K3. Next line contains N space separated integers.
Output
For each test case, output the K1th, K2th and K3th maximum sum in a single line, separated by a single space. See sample cases and explanation for more clarity.
Constraints
1 ? T ? 3
2 ? N ? 10000
1 ? K1 < K2 < K3 ? 2012
K3 ? N*(N+1)/2
-10000 ? A[i] ? 10000
Example
Input: 3 3 1 2 3 10 20 30 3 3 4 6 10 20 30 4 2 6 10 20 -15 10 -15 Output: 60 50 30 30 30 10 15 -5 -20
Explanation:
Case 1 & 2 : A = { 10, 20, 30 }. All possible sums of sub-arrays in non-increasing order, S[1..6] = { 60, 50, 30, 30, 20, 10 }
Warning : "Large input / output. Be careful with certain languages. Eg: Prefer using scanf/printf to cin/cout for C++"
Note : There are multiple test sets, and the judge shows the sum of the time taken over all test sets of your submission, if Accepted.
| Author: | flying_ant |
| Date Added: | 9-01-2012 |
| Time Limit: | 3 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
In the explanation, why is
@admin : Why am i being shown
@kewljerk : The subarray
A newbie here. Can anyone
@moawalling : Each test case
Still can't find out mistake
@nitishkr : Please do not ask
@admin Why does it show
i am not getting the pattern
http://www.codechef.com/wiki/
@saurabzx : The contest is
Is there any way to test this
@suhendry: The problems has
@suhendry: The problems has been moved into the practice section. You can submit your solutions there.
plz tell me why i am getting
@admin: how can i verify my