1656F - Parametric MST - CodeForces Solution

/* Author: BreakPlus */
#include<bits/stdc++.h>
using namespace std; typedef long long ll; typedef pair<ll,ll> P; typedef pair<pair<ll,ll>,ll> P3; typedef pair<pair<ll,ll>,pair<ll,ll> >P4;
#define mkp make_pair
#define fi first
#define se second
#define popcnt __builtin_popcount
#define pb emplace_back
const ll mod=998244353; const ll maxn=500005;

inline ll read(){ ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*f; }
inline ll lowbit(ll x){ return x&-x; }
struct Bit{
	ll c[maxn], _x[maxn], _w[maxn], tp=0;
	void update(ll x,ll w){ _x[++tp]=x, _w[tp]=w; while(x<maxn) c[x]+=w, x+=lowbit(x);} void update2(ll x,ll w){ while(x<maxn) c[x]+=w, x+=lowbit(x);}
	ll query(ll x){ ll res=0; while(x) res+=c[x], x-=lowbit(x); return res; }
	void clear(){ for(ll i=1;i<=tp;i++) update2(_x[i], -_w[i]); tp=0;} void fclear(){ tp=0; memset(c, 0, sizeof(c)); }
}bit;

inline ll maxx(ll a,ll b){ return a>b?a:b; } inline ll minn(ll a,ll b){ return a<b?a:b; }
inline void chkmax(ll &a,ll b){ a = maxx(a, b); } inline void chkmin(ll &a,ll b){ a = minn(a, b); }
inline void _Add(ll &a,ll b){ a+=b; if(a>=mod) a-=mod; } inline void _Minus(ll &a,ll b){ a-=b; if(a<0) a+=mod; }
inline ll Add(ll a,ll b){ a+=b; if(a>=mod) a-=mod; return a; } inline ll Minus(ll a,ll b){ a-=b; if(a<0) a+=mod; return a; }

inline ll qpow(ll a,ll b){ ll ans=1, base=a; while(b){ if(b&1) ans=1ll*ans*base%mod; base=1ll*base*base%mod; b>>=1; } return ans; }
struct Comb{
    ll fac[maxn], inv[maxn];
    Comb(){ fac[0]=1; for(ll i=1;i<=maxn-5;i++) fac[i]=1ll*fac[i-1]*i%mod; inv[maxn-5]=qpow(fac[maxn-5],mod-2); for(ll i=maxn-6;i>=0;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod; }
    ll C(ll a,ll b){ if(a<0 || b<0 || a<b) return 0; return 1ll*fac[a]*inv[b]%mod*inv[a-b]%mod; }
}comb;
ll Fac(ll x){return comb.fac[x];} ll iFac(ll x){return comb.inv[x];} ll Inv(ll x){return qpow(x, mod-2);}
/*--------------head------------------*/
void init(){

}
ll n,a[200005],sum; const double eps = 0.1;
// (a[i]+t) * (a[j]+t)

ll qz[200005];
void solve(){
    n=read();
    sum=0;
    for(ll i=1;i<=n;i++) a[i]=read(),sum+=a[i];
    sort(a+1, a+n+1);
    for(ll i=1;i<=n;i++) qz[i]=qz[i-1]+a[i];
    
    if(((n-2)*a[1]+sum) >0 ||  ((n-2)*a[n]+sum) < 0){
        puts("INF");
        return;
    }  
    // ll K=a[1]*(sum-a[1]) + a[n]*(sum-a[n]);
    ll ans = -1e18;
    for(ll i=1;i<=n;i++){
        // let -t = a[i]
        chkmax(ans, a[1]*(sum-qz[i]) + a[n]*(qz[i]-a[1]) -a[i]*( (i-1)*a[n] + qz[i]-a[1])-a[i]*( (n-i)*a[1]+sum-qz[i]));
    }
    printf("%lld\n", ans);
}
//#define FastIO
//#define OIcontest
int main(){
    #ifdef OIcontest
        freopen(".in","r",stdin); freopen(".out","w",stdout); 
    #endif
    #ifdef FastIO
        ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
    #endif
    init();
    ll T=read();
    while(T--) solve();
    return 0;
}
/*
Input1 Text Copied:


Answer1 Text Copied:


Input2 Text Copied:


Answer2 Text Copied:
*/