Dãy số hoàn hảo

Xem PDF




Thời gian:
Java 3.5s
Bộ nhớ:
Java 512M

Tác giả:
Dạng bài
Điểm: 300 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

Cho một dãy số nguyên \(a_1, a_2, a_3, …, a_n\) và một số nguyên \(k\). Một dãy con \(1 \leq i \leq j \leq n\) được gọi là hoàn hảo nếu như \(a_i + a_{i + 1} + a_{i + 2} + … + a_j = k\).

Yêu cầu: Hãy đếm xem có bao nhiêu dãy con hoàn hảo từ dãy đã cho.

Input

  • Dòng đầu tiên chứa số \(n \ (n \leq 10^5)\)\(k \ (|k| \leq 10^4)\) cách nhau bởi dấu cách.
  • Dòng tiếp theo chứa \(n\) số nguyên \(a_i \ (|a_i| \leq 10^4)\).

Output

  • Một số duy nhất là kết quả tìm được.

Scoring

  • Subtask \(1\) (\(50\%\) số điểm): \(n \leq 100\).
  • Subtask \(2\) (\(30\%\) số điểm): \(n \leq 5000\).
  • Subtask \(3\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input
5 5
1 2 3 4 5 
Output
2

Bình luận