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
DK...:
2019-04-18 01:40:59
The solution is more clear reversing the array |
|
buttman:
2016-07-27 17:15:11
@Shahbaz Khan Thanks, your commment helped.I almost gave up on finding a bug in my solution. |
|
ayush sinha:
2016-02-19 12:10:33
please explain o(n) approach a bit
|
|
Sreejato Bhattacharya:
2015-08-28 13:07:54
Nice problem!
|
|
Saksham :
2015-07-07 00:18:46
think of kadane
|
|
Petar Nyagolov:
2014-10-25 18:55:26
Can someone tell me how to solve it in O(n), please? |
|
Archit Jain:
2014-10-25 15:38:41
working for all the test cases specified in the comment and the forum still wa plz help |
|
ISHANI:
2014-10-02 07:07:48
awesome problem.No need for DP. |
|
kp:
2014-09-14 20:09:59
Even with o(n)..got TLE..any suggestions?? |
|
Shahbaz Khan:
2014-08-06 00:23:46
I got an O(n) solution, seems to be valid on all given and commented test cases. But still WA? And it does not need Fast IO. Am I doing it wrong?
|
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 |