Elearning CodePath – CTP Online Judge

Minimum Subarray Sum

GEN016

🟢 Hard #General #Two Pointers

### 📌 Thông tin chung

---
### 📝 Bài toán

Cho một dãy $N$ số nguyên dương $A = (A_1, A_2, \dots, A_N)$ và một số nguyên dương $S$.

Yêu cầu: Tìm **đoạn con liên tiếp** có **độ dài nhỏ nhất** sao cho tổng các số trong đoạn con đó **lớn hơn** $S$.

Nếu không có đoạn con nào thỏa mãn, kết quả là $0$.

---
### 📥 Định dạng Đầu vào

Dữ liệu vào từ file `BAI3.INP`:

* Dòng đầu: Gồm 2 số nguyên dương $N$ và $S$.
* Dòng tiếp theo: Gồm $N$ số nguyên dương $A_1, A_2, \dots, A_N$.

Giới hạn:
* $1 \le N \le 10^5$.
* $1 \le S \le 10^9$.
* $1 \le A_i \le 10^4$.

---
### 📤 Định dạng Đầu ra

Ghi ra file `BAI3.OUT` một số là độ dài nhỏ nhất tìm được.

---
### ✨ Ví dụ

| Input (`BAI3.INP`) | Output (`BAI3.OUT`) | Giải thích |
| :--- | :--- | :--- |
| `4 4` <br> `1 2 1 3` | `3` | Đoạn con: $(2, 1, 3)$, tổng $6 > 4$. Độ dài nhỏ nhất là $3$. |
| `2 3` <br> `1 1` | `0` | Tổng lớn nhất là $1+1=2$. $2 \not> 3$. Không có đoạn con nào thỏa mãn. |
| `3 5` <br> `1 2 3` | `3` | Đoạn con: $(1, 2, 3)$, tổng $6 > 5$. Độ dài nhỏ nhất là $3$. |

---
### 🏷 Subtask

| Subtask | Ràng buộc | Số điểm ước tính |
| :--- | :--- | :--- |
| 1 | $N \le 1000$ | $40\%$ |
| 2 | $N \le 10^5$, $S \le 10^9$ | $60\%$ |

---

✅ Đã AC: 3 / 11 submissions