TMSUM - The Maximize Sum
You are given a set S of n elements. Do you know how many subsets the set has? It is 2n where n is the number of elements in S.
For example, consider a set S of 3 elements. S = {1, 2, 3} so S has 23 = 8 subsets. They are {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 3}, {1, 2, 3}, { }. Here { } is empty set.
In the above example number of subsets of S having at most 2 elements excluding empty set are {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 3}.
Find subsets which have at most 2 elements excluding empty set in which each element of S must belong to a single a subset i.e. if we take subset for example {1} then we can’t take other subsets containing element 1. Now sum the product of the subsets containing 2 elements with the value of subsets containing single element. Your target will be maximizing this sum.
For example consider a set S= {1, 2, 3, 4, 5, 6}. So the subsets of S having at most 2 elements excluding the empty set are {1}, {2}, {3}, {4}, {5}, {6}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {2, 3}, {2, 4}, {2, 5}, {2, 6}, {3, 4}, {3, 5}, {3, 6}, {4, 5}, {4, 6}, {5, 6}.
Now we can take subsets of {5, 6}, {4, 3} and {1, 2} which contains all 6 elements of S then total sum will be = (5 * 6) + (4 * 3) + (1 * 2) = 44. On the other hand if we take subsets of {5, 6}, {4, 3} and {1} and {2} then total sum will be (5 * 6) + (4 * 3) + 1 + 2 = 45 which is greater than the previous one.
Input
The first line of the input will be an integer T to represent the number of test cases. For each case there will be two lines. The first line contains integer n — the number of distinct elements in the given set S. The second line contains n integers si (i = 1, 2 ... n) — the elements of the S.
Output
In a single line, output the maximum sum.
Constraints
- 1 ≤ T ≤ 100
- 1 ≤ n ≤ 100
- -10000 ≤ si ≤ 10000
Example
Input: 2 6 1 2 3 4 5 6 3 1 2 3 Output: 45 7
hide comments
slothsphereoj:
2024-03-20 07:42:48
Adhoc
|
|
adityaghosh96:
2017-06-21 17:04:49
adhoc
|
|
akt_1998:
2017-06-21 16:41:38
adhoc ;) |
|
aman_9899:
2017-06-21 11:37:55
dp... |
|
Siddharth Singh:
2016-06-09 15:19:03
A very peculiar Corner Case Costed Me 3-4 WA's
|
|
ALi Ibrahim:
2016-05-19 21:15:05
@Divyaanand Sinha
|
|
ALi Ibrahim:
2016-05-19 21:13:00
nice problem :D |
|
Divyaanand Sinha:
2016-05-18 18:43:57
are all the elements of the set distinct? Last edit: 2016-05-18 20:42:18 |
|
poojan :
2016-05-16 04:46:52
1 test case :
|
|
aditya730:
2016-04-28 13:19:38
I think one of the sample test cases gives way too much hint. |
Added by: | Akid Sultan |
Date: | 2016-04-27 |
Time limit: | 0.5s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU JS-MONKEY |
Resource: | Own problem. Used in NHSPC 2016 Final Round. More about NHSPC: http://www.nhspc.org/ |