WEIGHT - Weighted Sum

no tags 

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 :

  1. Each weight should be an positive integer.
  2. W[1] = 1
  3. 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
not getting

Sreejato Bhattacharya: 2015-08-28 13:07:54

Nice problem!

@Peter (**MAJOR SPOILER**): No matter what the sign of a[i] is, in the optimal solution weight[i] is either weight[i-1]+1 or 2-- it's easy to see why. :)

Last edit: 2015-08-28 13:43:19
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?

AC finally. Trivial mistake (long long = int*int prob) :)

Last edit: 2014-08-06 00:41:23

Added by:Kunal Jain
Date:2011-02-07
Time limit:0.280s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:CodeCraft 11