Elearning CodePath – CTP Online Judge

Đoạn Con Tổng Không Vượt Quá Tối Đa

LONGEST

🟢 Hard #Binary Search #Two Pointers #Sliding Window

### 📌 Thông tin chung

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

Cho dãy số nguyên $A = (a_1, a_2, \dots, a_N)$ và một số nguyên $S$.

Một dãy con liên tiếp của dãy số có dạng $A[i..j] = (a_i, a_{i+1}, \dots, a_j)$, với $1 \le i \le j \le N$.

* **Tổng** của dãy con là $Sum(i, j) = \sum_{k=i}^{j} a_k$.
* **Độ dài** của dãy con là $j - i + 1$.

Yêu cầu: Tìm độ dài lớn nhất của dãy con liên tiếp $A[i..j]$ sao cho tổng của nó không lớn hơn $S$.

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

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

* Dòng 1: Ghi hai số nguyên $N$ và $S$.
* Dòng 2: Ghi $N$ số nguyên $a_1, a_2, \dots, a_N$ cách nhau bởi dấu cách.

Giới hạn:
* $1 \le N \le 10^6$.
* $|a_i| \le 10^6$.
* $S$ là số nguyên ($S\le 10^{9}$).

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

Ghi ra file `LONGEST.OUT` một số nguyên duy nhất là độ dài dãy con liên tiếp lớn nhất thỏa mãn.

---
### ✨ Ví dụ

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

Giải thích:
* $N=8, S=7$.
* Đoạn con $A[3..7] = (-2, 4, -5, 1, 9)$ có tổng là $-2+4-5+1+9 = 7$. Độ dài là 5. $7 \le S$.
* Đoạn con $A[4..8] = (4, -5, 1, 9, 3)$ có tổng $4-5+1+9+3 = 12 > 7$.
* Đoạn con $A[1..8]$ có tổng $6+8-2+4-5+1+9+3 = 24 > 7$.
* Độ dài lớn nhất là 5.

---
### 🏷 Phân Subtask

Do $N$ có thể lên đến $10^6$, thuật toán $O(N)$ là bắt buộc.

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

✅ Đã AC: 1 / 21 submissions

📘 Lời giải