Bài 6.4. Kho Báu Mạo Hiểm: Tìm Kiếm Hầm Mỏ Ẩn - [Độ khó: Khá]

Mô tả bài tập: Bạn là một nhà thám hiểm tài ba, chuyên đi tìm kiếm các kho báu bị chôn vùi trong các hầm mỏ cổ đại. Mỗi hầm mỏ được mô tả như một dãy số nguyên, trong đó mỗi số thể hiện giá trị tài nguyên mà bạn có thể tìm thấy tại một khu vực nhất định. Nhiệm vụ của bạn là tìm tất cả các "khu vực kho báu tiềm năng". Một khu vực được coi là kho báu tiềm năng nếu nó là một dãy con liên tiếp (contiguous subarray) mà tổng giá trị tài nguyên của nó nằm trong một khoảng cho trước [MinSum, MaxSum]. Bạn cần đếm xem có bao nhiêu khu vực kho báu tiềm năng như vậy.

INPUT FORMAT

Dòng đầu tiên chứa ba số nguyên N, MinSum, MaxSum (1 <= N <= 1000, -1000000 <= MinSum <= MaxSum <= 1000000). Dòng thứ hai chứa N số nguyên A_1, A_2, ..., A_N (-1000 <= A_i <= 1000), là giá trị tài nguyên tại các khu vực.

OUTPUT FORMAT

In ra một số nguyên duy nhất là tổng số lượng dãy con liên tiếp có tổng nằm trong khoảng [MinSum, MaxSum].

Ví dụ:

Input:

5 3 6
1 2 3 4 5

Output:

6

Giải thích: Các dãy con liên tiếp và tổng của chúng, kiểm tra xem tổng có nằm trong khoảng [3, 6] hay không:

• [1] -> Tổng: 1
• [2] -> Tổng: 2
• [3] -> Tổng: 3 (Thỏa mãn 3 <= 3 <= 6) -> Đếm 1
• [4] -> Tổng: 4 (Thỏa mãn 3 <= 4 <= 6) -> Đếm 2
• [5] -> Tổng: 5 (Thỏa mãn 3 <= 5 <= 6) -> Đếm 3
• [1, 2] -> Tổng: 3 (Thỏa mãn 3 <= 3 <= 6) -> Đếm 4
• [2, 3] -> Tổng: 5 (Thỏa mãn 3 <= 5 <= 6) -> Đếm 5
• [3, 4] -> Tổng: 7
• [4, 5] -> Tổng: 9
• [1, 2, 3] -> Tổng: 6 (Thỏa mãn 3 <= 6 <= 6) -> Đếm 6
• [2, 3, 4] -> Tổng: 9
• [3, 4, 5] -> Tổng: 12
• [1, 2, 3, 4] -> Tổng: 10
• [2, 3, 4, 5] -> Tổng: 14
• [1, 2, 3, 4, 5] -> Tổng: 15

Tổng cộng có 6 dãy con liên tiếp thỏa mãn điều kiện.