VOI 06 Bài 7 - Dãy con dài nhất

View as PDF

Submit solution


Points: 0.12 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Ðề thi quốc gia 2006
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho dãy số nguyên ~a_{1}~, ~a_{2}~, ..., ~a_{n}~.

Dãy số ~a_{i}~, ~a_{i + 1}~, ..., ~a_{j}~ với ~1 \leq i \leq j \leq n~ được gọi là dãy con của dãy số đã cho và khi đó, ~j-i + 1~ được gọi là độ dài, còn ~a_{i} + a_{i~ + ~1}~ ...~+ a_{j}~ được gọi là trọng lượng của dãy con này.

Yêu cầu: cho số nguyên ~p~, trong số các dãy con của dãy số đã cho có trọng lượng không nhỏ hơn ~p~ hãy tìm dãy con có độ dài lớn nhất.

Input

  • Dòng đầu tiên ghi hai số nguyên ~n~ và ~p~ cách nhau bởi dấu cách.
  • Dòng thứ ~i~ trong số ~n~ dòng tiếp theo chứa số nguyên ~a_{i}~ là số hạng thứ ~i~ của dãy số đã cho, ~i = 1~, ~2~, ..., ~n~.

Output

Ghi ra số nguyên ~k~ là độ dài của dãy con tìm được (qui ước: nếu không có dãy con nào thỏa mãn điều kiện đặt ra thì ~k = -1)~.

Giới hạn

  • Trong tất cả các test: ~1 \leq n \leq 50000~; ~|a_{i}| \leq 20000~; ~|p| \leq 10^{9}~.
  • Có ~50\%~ số lượng test với ~n \leq 2000~.

Sample Input 1

5 6
-2
3
2
-2
3

Sample Output 1

4

Sample Input 2

4 9
2
3
2
-2

Sample Output 2

-1

Comments

Please read the guidelines before commenting.



  • -6
    hoang_thanh_dat  commented on Sept. 9, 2022, 1:22 p.m. edited

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -1
      nguyenhainam1012cg  commented on March 14, 2023, 1:51 p.m.

      dùng segment tree để cắn đc nlogn còn n thì chịu =)))


    • -1
      vodanhdamcontest  commented on Jan. 10, 2023, 12:44 p.m.

      O(n^2) nhưng cũng tùy bạn của bạn cài đặt nhé. Nếu bạn ý viết tối giản thì AC cũng không quá là khó!