giúp mình với, viết trên C++

Tiến hành:

Bước 1: Tạo một mảng có cùng kích thước với một mảng đã cho có chỉ số thứ i giữ giá trị của tổng các phần tử từ chỉ số 0 đến i của mảng đã cho. Hãy gọi nó là mảng tiền tố

Bước 2: Tạo một mảng khác có cùng kích thước với một mảng đã cho có chỉ số thứ i là giá trị của tổng các phần tử từ chỉ số i đến n-1 của mảng đã cho. Hãy gọi nó là mảng hậu tố.

Bước 3: Vì vậy, chúng ta bắt đầu duyệt qua mảng tiền tố và giả sử tại chỉ số thứ i của mảng tiền tố, giá trị của mảng tiền tố bằng (tổng tất cả các phần tử của mảng đã cho) / 3.

Bước 4: Đối với i được tìm thấy ở bước trên, chúng ta xem xét mảng hậu tố từ chỉ số thứ (i + 2) và bất cứ nơi nào giá trị của mảng hậu tố bằng (tổng tất cả các phần tử của mảng đã cho) / 3, chúng ta tăng biến đếm bằng 1.

Tối ưu:

Phương pháp Tiếp cận Hiệu quả [Giải pháp O (n)]:

1.Nếu tổng tất cả các phần tử của mảng không chia hết cho 3 thì trả về 0.

2.Rõ ràng là tổng của mỗi phần của mỗi phần liền kề sẽ bằng tổng của tất cả các phần tử chia cho 3.Hãy tạo một mảng cnt [], trong đó cnt [i] bằng 1, nếu tổng các phần tử từ thứ i đến thứ n bằng Array_Sum / 3 else 0. Bây giờ, hãy tính tổng tích lũy của mảng cnt từ chỉ số cuối cùng .

4.Do đó, chúng ta nhận được giải pháp rất đơn giản: với mỗi tiền tố của mảng ban đầu 1… i với tổng bằng Array_Sum / 3, chúng ta cần thêm vào câu trả lời tổng [i + 2].

code c++:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll countways(ll a[], ll n)
{
    ll cnt[n] = {0}, s = 0;
     
  
    for (ll i = 0 ; i < n ; i++)
    {
        s += a[i];
    }

    if (s % 3 != 0)
        return 0;
     
 
    s /= 3;
     
    ll ss = 0;
     
   
    for (ll i = n-1; i >= 0 ; i--)
    {
        ss += a[i];
        if (ss == s)
            cnt[i] = 1;
    }
     
   
    for (ll i = n-2 ; i >= 0 ; i--)
        cnt[i] += cnt[i + 1];
     
    ll ans = 0;
    ss = 0;
     
   
    for (ll i = 0 ; i+2 < n ; i++)
    {
        ss += a[i];
        if (ss == s)
            ans += cnt[i + 2];
    }
    return ans;
}
 

int main()
{
    ll n;
    cin>>n;
    ll arr[n+1];
    for (ll i = 0 ; i < n ; i++) cin>>arr[i];
    
    cout << countways(arr, n) << endl;
    return 0;

//dotetoanhoc
}