Elearning CodePath – CTP Online Judge

Phân đoạn

SEQPART

🟢 Hard #Greedy

### 📌 Thông tin chung

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

Cho dãy số nguyên $A = (a_1, a_2, \dots, a_n)$ và số nguyên $m$.
Yêu cầu: Chia dãy $A$ thành một số **ít nhất** các đoạn con liên tiếp sao cho **tổng các phần tử trong mỗi đoạn con không vượt quá $m$**.

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

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

* Dòng 1: Chứa hai số nguyên dương $n$ và $m$.
* Dòng 2: Chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ cách nhau bởi dấu cách.

Giới hạn:
* $n \le 10^5$.
* $m \le 10^9$.
* $|a_i| \le 10^9$.
* Dữ liệu đảm bảo luôn có kết quả.

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

Ghi ra file `SEQPART.OUT` một số nguyên duy nhất là số đoạn ít nhất tìm được.

---
### ✨ Ví dụ

| Input (`SEQPART.INP`) | Output (`SEQPART.OUT`) |
| :--- | :--- |
| `11 5` <br> `9 -1 2 -6 1 2 3 -4 3 9 -4` | `3` |

Giải thích:
$A = (9, -1, 2, -6, 1, 2, 3, -4, 3, 9, -4)$, $m=5$.
Cách chia tối ưu:
1.  Đoạn 1: $(9, -1, 2, -6, 1) \rightarrow$ Tổng $9-1+2-6+1 = 5 \le 5$.
2.  Đoạn 2: $(2, 3, -4, 3) \rightarrow$ Tổng $2+3-4+3 = 4 \le 5$.
3.  Đoạn 3: $(9, -4) \rightarrow$ Tổng $9-4 = 5 \le 5$.
Tổng số đoạn ít nhất là $3$.

---
### 🏷 Subtask

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

---

✅ Đã AC: 1 / 4 submissions