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

View as PDF
Submit solution
Points: 0.08 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout
Problem source:
Ðề thi quốc gia 2006
Problem types
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, 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.


  • 5
    Duke_Verstappen  commented on Nov. 29, 2025, 7:42 a.m.

    tôi đã suy nghĩ bài này trong 36 tỷ năm, làm được 360 dòng code, tôi vận dụng hết 36 kế sách tôi tự nghĩ ra và tôi chỉ đúng được 36 test nhất định mà do tôi tự nghĩ ra tôi đã submit bài này 36 lần và cả 36 lần ko lần nào đúng


  • -5
    phannam310810  commented on July 23, 2025, 2:53 a.m.

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


  • -3
    haitin9Aps  commented on Feb. 22, 2025, 8:18 a.m.

    oách xà lách vô cùng


    • 2
      Duke_Verstappen  commented on Nov. 29, 2025, 7:39 a.m.

      tôi cũng thích ăn salad


  • 6
    melondepchai  commented on Aug. 29, 2024, 5:43 a.m.

    Chúc các bạn một ngày tốt lành:33


  • -7
    thanhtamido0  commented on Aug. 27, 2024, 9:48 a.m.

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


    • -11
      TSTD_TrinhKhanhHung  commented on Aug. 28, 2024, 7:18 a.m.

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


  • -17
    nb_lehongphong_dangnhatnguyen  commented on May 18, 2024, 8:00 a.m.

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


  • -6
    DIEM10CODER  commented on Feb. 27, 2024, 12:25 p.m.

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


  • -10
    nb_lhp_ntminh  commented on Feb. 16, 2024, 9:13 a.m.

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


  • -38
    modwwe  commented on Sept. 12, 2023, 12:38 a.m.

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


  • -11
    hoongquaan  commented on Sept. 12, 2023, 12:31 a.m. ← edit 3

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


  • -12
    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.


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

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


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

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