#1337. DIV4 - Chia dãy

Bộ nhớ: 256 MiB Thời gian: 500 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Nguồn: Bài tập thầy Nguyễn Thanh Bình Ôn ĐT Hải Phòng T10/2020

Cho dãy số nguyên A=(a_1,a_2,…,a_n) . Hãy đếm số cách chia dãy trên thành 4 dãy con gồm các số liên tiếp của A sao cho tổng các số trong mỗi dãy con này đều bằng nhau. Chính xác hơn, mỗi cách chia được mô tả bằng bộ 3 chỉ số (i,j,k):1≤i<j<k≤n . Khi đó:

  • (a_1,a_2,…,a_i) là dãy thứ nhất
  • (a_(i+1),…,a_j) là dãy thứ hai
  • (a_(j+1),…,a_k) là dãy thứ ba
  • (a_(k+1),…,a_n) là dãy thứ tư.

Hai cách chia được gọi là khác nhau nếu nó ứng với hai bộ ba chỉ số (i,j,k) khác nhau.

Dữ liệu vào:

  • Dòng đầu tiên chứa số nguyên dương n\ (n≤10^6) ;
  • Dòng thứ hai chứa n số nguyên a_1,a_2,…,a_n\ (|a_i|≤10^9) hai số liên tiếp cách nhau bằng dấu trống.

Dữ liệu ra:

  • Một số nguyên là số lượng cách chia tìm được;

Giới hạn:

  • Subtask \#1: 20\% số điểm có n≤500 ;
  • Subtask \#2: 30\% số điểm khác có n≤5000 ;
  • subtask \#3: 50\% số điểm còn lại có n≤10^6 .

Ví dụ:

Dữ liệu vào:
8
1 1 1 1 1 1 1 1
Dữ liệu ra:
1