MAXSUB - Maximum Subset of Array

no tags 

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..
whats the answer for :
1.) -1 -1 -1 0 0
2.) 0 0 0 2 3

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?

whats the answer for :
1.) -1 -1 -1 0 0
2.) 0 0 0 2 3
?

Last edit: 2011-06-20 20:35:32
chinmay chauhan: 2011-06-04 16:17:46

could u please post some more test cases
the question is not quite clear
what does this mean "sum of the maximum non-empty subset"
in this case what does "maximum" non-empty subset mean ??

Last edit: 2011-06-05 05:16:13
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.........
I don't know what made me feel , that I should print "the value of the maximum subset" modulus 1000000009.........

[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.

Re: Patrik: I wouldn't call it trival. It's very simple, but the CATCH is easy to miss. I almost fell for it myself :)
Re Re: Fair enough. I deliberately removed a critical case from sample output. This was actually for a contest for beginners, very adhoc but I guess falls in somewhere in between trivial and non-trivial.

Last edit: 2011-03-09 19:18:24

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