题解 | 牛牛与切割机

#include <stdio.h>
#include <stdlib.h>
typedef long long ll;

int compare(const void*a, const void*b){
    ll va = *(ll*)a;
    ll vb = *(ll*)b;
    if (va < vb) return -1;
    if (va > vb) return 1;
    return 0;
}
int main(void) {
    int n;
    scanf("%d", &n);

    int*a = (int*)malloc(n * sizeof(int));
    ll*prefix = (ll*)malloc((n+1) * sizeof(ll)); 
    prefix[0] = 0;
    for(int i = 0; i < n; i++){
        scanf("%d", &a[i]);
        prefix[i+1] = prefix[i] + a[i];
    }
    ll res = 0;
    int r = 0;
    ll max = 0;
    ll sum[1000005];
    for(int r = 0; r < n; r++){
        res = prefix[n] - prefix[r+1];    //后半部分总和
        sum[r] = res * prefix[r + 1];
    }
    qsort(sum, n, sizeof(ll), compare);
    printf("%lld", sum[1]);

    free(a);
    free(prefix);
    return 0;
}