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++, 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.


  • -1
    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


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

    bài này tôi 2 for cũng ăn được;))


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

      uầy cảm ơn bạn đã chia sẻ 1 thuật toán đỉnh cao, nhờ vào thuật toán của bạn, loài người đã có sự phát triển vượt bật, có thể dự đoán tương lai, giải quyết nhiều vấn đề xã hội,.... .Tôi đề nghị bạn cần được trao giải Nobel nhờ phát minh này....


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


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

    hôm nay em tuyệt lắm (bài này :)))


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


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

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


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


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


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

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


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

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