MAXSUB - Maximum Subset of Array
Given an array find the sum of the maximum non-empty subset of the array and also give the count of the subset. A subset of an array is a list obtained by striking off some (possibly none) numbers.
A non-empty subset implies a subset with at least 1 element in it.
Input
First line contains an integer T which is the number of integers. Following this T-cases exist.
Each case starts with a line containing an integer n which is the number of elements in the array.
The next line contains n-integers which contain the value of this subset.
Constraints
T <= 20
n <= 50,000
Each element in the array <= 1,000,000,000
Output
For each test case output the value of the maximum subset and the count of the subsets modulo 1000,000,009
Example
Input: 2 5 1 -1 1 -1 1 6 -200 -100 -100 -400 -232 -450 Output: 3 1 -100 2
hide comments
rahul singh:
2012-01-20 03:55:43
what is the ansewer for..
|
|
Ajey Golsangi:
2012-01-10 15:53:39
@Gurpreet Singh : I committed the same mistake as you. |
|
ganu:
2011-06-07 08:31:13
getting WA and unable to figure out the problem...works fine for the above test cases. Anything that I might be ovelooking?
|
|
chinmay chauhan:
2011-06-04 16:17:46
could u please post some more test cases
|
|
Suprabh Shukla:
2011-05-28 14:52:55
@Gurpreet: Dude I read your comment about ten times yet I submitted the code with that same mistake about ten times :D |
|
biQar:
2011-03-28 11:07:27
nice one !! :) |
|
Gurpreet Singh:
2011-03-25 11:56:01
huufffff!!!!! relieved.........
|
|
[Retired] Fendy Kosnatha:
2011-03-10 09:40:29
Re: Censored. Such outputs will spoil the problem, it is really trivial anyway. Last edit: 2011-03-10 14:49:01 |
|
[Retired] Fendy Kosnatha:
2011-03-09 18:18:18
can you explain where you get that output (not the algo)? |
|
:D:
2011-03-09 17:31:13
Just the number of different subsets should be outputted modulo 10^9+9.
|
Added by: | .:: Pratik ::. |
Date: | 2011-03-07 |
Time limit: | 0.507s-2.450s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |