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
Albert Chen:
2012-02-01 16:55:22
@pvr_nrt I misunderstand your question... It's sort of DP, but not typical. Last edit: 2012-02-01 19:55:47 |
|
pvr_nrt:
2012-01-30 18:26:14
@Albert Chen is it DP ? Last edit: 2012-01-30 18:28:50 |
|
Albert Chen:
2011-11-29 03:36:23
I felt %^&* good when I figured it out...
|
|
Chandan Giri:
2011-09-09 08:32:23
nice problem :) |
|
Gurpreet Singh:
2011-09-03 07:31:24
Yeah!! I have to analyse the cases for longgg time. nice and easy problem. |
|
akshay verma:
2011-06-29 13:55:30
more testcases please!! |
|
Garg Ankit:
2011-04-17 19:29:34
plzz provide more test cases..
|
|
el moatasem:
2011-04-14 10:23:46
I do it in O(n) in pyth and cpp
|
|
vg88:
2011-02-17 08:57:28
what order recquire for this problem
|
|
:D:
2011-02-10 19:21:33
That's a part of this problem, you have to answer it yourself. Don't try to guess lemats for the task! |
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 |