Mandragora Forest

                            Solution in C :

In C++ :





#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

using ll = long long;


int main() {
    int T;
    cin >> T;
    while (T--) {
        int N;
        cin >> N;
        vector<ll> H(N, 0LL);
        for (int i = 0; i < N; ++i) cin >> H[i];
        
        sort(H.begin(), H.end());
        for (int i = N - 2; i >= 0; --i) H[i] += H[i + 1];
        
        ll ans = 0LL;
        for (int i = 0; i < N; ++i) {
            ans = max(ans, ll(i + 1) * H[i]);
        }
        cout << ans << endl;
    }
    return 0;
}








In Java :





import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for (int testCase = 0; testCase < t; testCase++) {
            int n = in.nextInt();
            List<Long> healths = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                healths.add(in.nextLong());
            }
            Collections.sort(healths);
            long maxExp = 0;
            long totalHealth = 0;
            long totalStrength = n + 1;
            for (int i = n - 1; i >= 0; i--) {
                totalStrength--;
                totalHealth += healths.get(i);
                long exp = totalStrength * totalHealth;
                if (exp > maxExp) {
                    maxExp = exp;
                }
            }
            System.out.println(maxExp);
        }
    }
}








In C :





#include<stdio.h>
#include<stdlib.h>
typedef long long unsigned llu;
typedef unsigned u;
int F(const void*x,const void*y){return*(int*)x-*(int*)y;}
u H[111111];llu S[111111];
int main()
{
	u t,n,i,k;llu r,x,y;
	for(scanf("%u",&t);t--;)
	{
		scanf("%u",&n);k=1;r=0;
		for(i=-1;++i<n;)scanf("%u",H+i);
		qsort(H,n,sizeof(u),F);
		for(S[i=n]=0;i--;)S[i]=S[i+1]+H[i];
		for(i=-1;++i<n;)
		{
			x=S[i]*k;
			y=S[i+1]*(k+1);
			if(y>x)++k;
			else r+=H[i]*(llu)k;
		}
		printf("%llu\n",r);
	}
	return 0;
}








In Python3 :





def main():
    t = int(input())
    while t > 0:
        n = int(input())
        a = list(map(int, input().split()))
        a.sort()
        b = a[:]
        for i in range(n - 2, -1, -1):
            b[i] = a[i] + b[i + 1]
        
        ans = b[0]
        for i in range(n):
            ans = max(ans, (i + 1) * b[i])
            
        print(ans)
        t -= 1

main()