Dãy số hoàn hảo

View as PDF




Time limit:
Java 3.5s
Memory limit:
Java 512M

Author:
Problem types
Points: 300 (p) Time limit: 1.0s Memory limit: 1023M Input: stdin Output: stdout

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

Comments