暴力法O(n^2)无法AC 采取前缀和优化 sum[i] = sum[i-1] + a[i]

模拟n=4 a1 a2 a3 a4,结果为

a1a2 + a1a3 + a1a4 + a2a3 + a2a4 + a3a4 = a1(s4-s1) + a2(s4-s2) + a3(s4-s3)

总结为 a[i]*(s[n] - s[i])

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
LL a[200010],sum[200010];
int main()
{
    LL n;
    scanf("%ld",&n);

    for(LL i = 1;i<=n;i++) 
    {
        scanf("%ld",&a[i]);
        sum[i] = sum[i - 1] + a[i];
    }

    LL total = 0;

    for(LL i = 1;i<=n-1;i++)
    {
        total += a[i]*(sum[n] - sum[i]);
    }
    printf("%ld",total);
    return 0;
}