Codeforces 466C Number of Ways(高效)

題目連結：Codeforces 466C Number of Ways

題目大意：給定一個序列，要求分成三段，每段和相同，問有多少種拆分方法。

解題思路：将所有字首和為sum3的位置全部記錄下來，然後在逐個計算字尾和，然後對應如果和為sum3，計算該位置前有多少個字首和sum3。

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;
const int maxn =  *  + ;

int n, arr[maxn];
ll s = ;
vector<int> vec;

ll solve () {
    if (s % )
        return ;

    s /= ;
    ll p = , ret = ;

    for (int i = ; i < n; i++) {
        p += arr[i];
        if (p == s)
            vec.push_back(i);
    }

    p = ;
    for (int i = n-; i >= ; i--) {
        p += arr[i];
        if (p == s)
            ret += lower_bound(vec.begin(), vec.end(), i-) - vec.begin();
    }
    return ret;
}

int main () {
    scanf("%d", &n);

    for (int i = ; i < n; i++) {
        scanf("%d", &arr[i]);
        s += arr[i];
    }
    printf("%lld\n", solve());
    return ;
}