WEIGHT - Weighted Sum
You are given N integers, A[1] to A[N]. You have to assign weights to these integers such that their weighted sum is maximized. The weights should satisfy the following conditions :
- Each weight should be an positive integer.
- W[1] = 1
- W[i] should be in the range [2, W[i-1] + 1] for i > 1
Weighted sum is defined as S = A[1] * W[1] + A[2] * W[2] + ... + A[N] * W[N]
Input
There are multiple test cases.
First line contains the number of test cases
Each test case consists of a single line containing N.
This is followed by N lines, each containing A[i]
Output
For each test case, output one line - the maximum weighted sum.
Example
Input:
1
4
1
2
3
-4
Output: 6
Explanation
The weights are 1, 2, 3, 2.Constraints
N <= 10^6
| A[i] | <= 10^6
Total number of test cases is around 10.
hide comments
Ivan Sto¹iæ:
2014-05-05 04:02:19
Nice one!
|
|
Bhavik:
2013-12-20 15:35:11
all test cases given(also in comments) are working fine,,,,even took long long but stil WA!!!!
|
|
ROHIT RAWAT:
2013-11-01 08:00:57
program is working for sample test case and the cases provided by Albert Chen. Still getting WA.
|
|
Srijan Khare:
2013-05-30 12:35:35
nice problem... |
|
ANKIT KUMAR SRIVASTAVA:
2013-03-22 13:38:22
finally i did it,think as AD-HOC friends |
|
Akshay Kumar:
2012-12-20 20:41:47
use long long int for number of test cases and number of elements,got 3 WA coz of that |
|
Abhik Mondal:
2012-07-02 12:32:11
any reason for a seg fault? |
|
Piyush Kapoor:
2012-06-15 20:09:55
nice problem!! :D |
|
Sahil Garg:
2012-05-11 06:34:24
working for the above test case.. still WA |
|
yo :P:
2012-03-31 22:07:37
thnx aman kumar :) |
Added by: | Kunal Jain |
Date: | 2011-02-07 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | CodeCraft 11 |