Đoạn con ngắn nhất có tổng ít nhất K (Shortest Subarray with Sum at Least K)

Nguồn: LeetCode

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho mảng số nguyên nums và số nguyên dương $K$.

Hãy tìm độ dài nhỏ nhất của một đoạn con liên tiếp không rỗng có tổng ít nhất $K$.

Nếu không tồn tại đoạn nào thỏa mãn, in -1.

Bài gốc trên LeetCode được cho dưới dạng hàm. Phiên bản Phước Hưng OJ chuyển sang định dạng nhập/xuất chuẩn với một test case trong mỗi file.

Input

• Dòng đầu chứa hai số nguyên $n,K$.
• Dòng thứ hai chứa $n$ số nguyên $nums_1,nums_2,\ldots,nums_n$.

Output

In độ dài nhỏ nhất của một đoạn con có tổng ít nhất $K$. Nếu không có đoạn phù hợp, in -1.

Subtask

Điều kiện chung đã đối chiếu với nguồn:

• $1\le n\le10^5$

• $-10^5\le nums_i\le10^5$

• $1\le K\le10^9$

• LeetCode là bài dạng hàm; bản Phước Hưng OJ chuẩn hóa thành một test stdin/stdout.

• Subtask 1 — 20%: $n\le40$

• Subtask 2 — 30%: Mọi phần tử đều không âm: $nums_i\ge0$.

• Subtask 3 — 50%: không có điều kiện bổ sung ngoài các điều kiện chung ở trên.

Ví dụ

Input

3 3
2 -1 2

Output

3

Giải thích

Với dãy

và $K=3$, toàn bộ đoạn $[1,3]$ có tổng

nên độ dài $3$ là hợp lệ.

Mọi đoạn có độ dài $1$ hoặc $2$ đều có tổng nhỏ hơn $3$, vì vậy độ dài nhỏ nhất là $3$.