Giải bài trực tuyến

Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

Từ tập các bài có trên SPOJ (oi)

2250. Dãy con dài nhất

Mã bài: NKMAXSEQ

Cho dãy số nguyên a1, a2, …, an.

Dãy số ai, ai+1, …, aj với 1 ≤ i ≤ j ≤ 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 ai+ai+1...+aj ượ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ố cc dãy con của dãy số ã cho c trọng lượng khng nhỏ hơn p hãy tìm dãy con c ộ dài lớn nhất.

Dữ liệu vào

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

Kết qủa

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

Hạn chế

Trong tất cả cc test: 1 ≤ n ≤ 50000; |ai| ≤ 20000; |p| ≤ 109. C 50% số lượng test với n ≤ 2000.

V dụ

Dữ liệu mẫu
5 6
-2
3
2
-2
3

Kết qủa
4

Dữ liệu mẫu
4 9
2
3
2
-2

Kết qủa
-1

Được gửi lên bởi:Duc
Ngày:2007-12-27
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL JS NODEJS PERL 6
Nguồn bài:ề thi quốc gia 2006

hide comments
2014-07-28 05:58:15 Nguyễn Vn oàn
Ai huong dan minh lam dc 100d vs
2014-07-26 11:51:27 »*-..©ªø..-*«
hjhj . minh AC roi cac ban oi ! lam hoai moi phat hien QHD (y)
2014-04-26 04:24:14 Hồng ào
bài này dùng thuật ton gì ể n hết 100 iểm vậy?
2014-01-11 16:41:56 Bùi Cng Lộc
sao O(n) mà ṽn 10 hoài ṿy... chán bài này ghê
2013-08-31 10:57:41 nguyễn vn khi
Sao O(n) mà c 20 iểm vậy?
2013-05-25 03:26:40 Lê Thanh Tùng
bài này p dụng kiểu quy hoạch ộng mà ược 60 iểm :))
2013-05-15 08:29:52 ๖ۣۜLove๖ۣۜ
may Pyramid (Intel Pentium III 733 MHz)
cham thi O(n^2) chay qua thoi gian nhu thuong
2013-02-01 12:45:39 Fallen Angel
dùng cch khoa học O(2N) vậy mà sao chỉ dk 10 iểm vậy , test 50k chạy ngon lành chưa tới 1s mà >.<
2012-12-17 16:34:50 Ồ lê aaaaaà...
duyệt tru ko ược u :P
2012-04-26 17:01:49 Gầy :))
Bai nay la doan con ma-(^^)-
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.