Elearning CodePath – CTP Online Judge

Kích thước mảng con lớn nhất

MaxiSubArr

🟢 Medium #Prefix Sum #Binary Search #Combinatorics #Sliding Window

### 📌 Thông tin chung

---
### 📝 Định nghĩa và Yêu cầu

Cho dãy $A$ gồm $N$ phần tử số nguyên dương và một số nguyên dương $K$.

Yêu cầu: Tìm kích thước $L$ lớn nhất ($1 \le L \le N$) sao cho tất cả các mảng con liên tiếp có kích thước $L'$ bé hơn $L$ ($1 \le L' < L$) đều có tổng các phần tử nhỏ hơn $K$.

Điều kiện thỏa mãn cho $L$:
$$\forall L' \in \{1, 2, \dots, L-1\}: \left( \max_{1 \le i \le N-L'+1} \left( \sum_{j=i}^{i+L'-1} A_j \right) < K \right)$$

Nếu không tồn tại kích thước $L \ge 1$ nào thỏa mãn (ví dụ: ngay cả độ dài $L'=1$ đã có tổng $\ge K$), kết quả là $-1$.

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

Tìm $L_{\max} \in [1, N]$ lớn nhất sao cho tất cả các tổng của các mảng con liên tiếp có độ dài từ $1$ đến $L_{\max}-1$ đều nhỏ hơn $K$.

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

* Dòng thứ nhất chứa số nguyên $N$ (độ dài dãy) và số nguyên $K$ (ngưỡng tổng).
* Dòng thứ hai ghi $N$ số nguyên thuộc dãy, các số cách nhau bởi dấu cách.

Giới hạn:
* $N \le 10^6$.
* $K \le 10^{12}$.
* $A_i \ge 1$ (Số nguyên dương).

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

Ghi kích thước mảng con lớn nhất $L$ cần tìm.

---
### ✨ Ví dụ

| MaxiSubArr.inp | MaxiSubArr.out | Giải thích |
| :---: | :---: | :--- |
| `4 8` <br> `1 2 3 4` | $\mathbf{3}$ | $\max(\text{sum}_{L'=1})=4 < 8$. $\max(\text{sum}_{L'=2})=7 < 8$. $\max(\text{sum}_{L'=3})=9 \ge 8$. $\to$ Kích thước lớn nhất $L$ sao cho mọi đoạn con $<L$ đều có tổng $<8$ là $L=3$. |
| `4 8` <br> `1 2 10 4` | `-1` | $\max(\text{sum}_{L'=1}) = 10$. $10 \not< 8$. $\to$ Không có dãy con thỏa mãn yêu cầu. |

---
### 🏷 Ràng buộc

| Subtask | Ràng buộc $N$ |  Tỷ lệ điểm |
| :--- | :--- | :--- | :--- |
| $1$ | $N \le 1000$ | $30\%$ |
| $2$ | $N \le 10^6$ |  $70\%$ |

---

✅ Đã AC: 0 / 0 submissions