\(i < j\) なる全ての \(i,j\) の組について愚直に \(A_iA_j\) の値を計算していると、計算量が \(O(N^2)\) となってしまい間に合いません。したがって、何らかの高速化を行う必要があります。

少し唐突ですが、\(i=1,2,\dots,N\) それぞれについて、\(S_i=A_1+A_2+\dots+A_i\) と定義します。すると、

\(\displaystyle \sum_{1\leq i< j\leq N} A_iA_j = \sum_{j=2}^{N}\sum_{i=1}^{j-1} A_iA_j = \sum_{j=2}^{N}\left(A_j\cdot\left(\sum_{i=1}^{j-1} A_i\right)\right)=\sum_{j=2}^{N}A_jS_{j-1}\)

となるため、数列 \(S=(S_1,S_2,\dots,S_N)\) の各要素の値を事前に求めておけば、\(O(N)\) で答えを計算することができます。

数列 \(S\) の各要素の値については、\(S_{i+1}=S_i+A_{i+1}\) という式によって \(S_i\) の値から \(S_{i+1}\) の値が簡単に求まることを利用し、\(S_1,S_2,\dots,S_N\) の順に求めていくと、\(O(N)\) で全ての値を求めることができます。（これは 累積和 とよばれる非常に重要なアルゴリズムです。）

よって、累積和を用いることで、全体で \(O(N)\) の計算量で本問題を解くことができました。

なお、下記の実装例のように、数列 \(S\) を陽に構築せず、答えの計算と各 \(S_i\) の値の計算を同時に行うこともできます。

実装例 (C++) :

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    ll ans = 0, sum = 0;
    for (int i = 0; i < n; i++) {
        ans += sum * a[i];
        sum += a[i];
    }

    cout << ans << endl;
}