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

NKMAXSEQ - Dãy con dài nhất

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/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ố 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.

Dữ liệu vào

  • 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 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 không 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ả các 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:Jimmy
Ngày:2007-12-27
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Đề thi quốc gia 2006

hide comments
2017-06-09 12:09:39
2 mang:sum+minsum sau do chatnp => CA

Last edit: 2017-06-09 12:12:02
2017-06-09 11:36:31
30 có phải AC ko vậy?
2016-10-04 14:07:44
prefix sum + chặt nhị phân AC. Mà bài này qhd kiểu gì nhỉ
2016-02-10 02:49:07
đã AC =
- trâu bò (2 dòng for) 3s
- Bit 0.5s

Last edit: 2016-05-14 10:48:45
2015-12-02 04:44:18 Khanh Ninh
Đề nghị để time chặt hơn, n^2 AC @@!
2015-11-27 03:30:27 .
QHĐ giống bài dãy con có tổng lớn nhất rồi chặt nhị phân
2015-10-09 15:53:57
nh?t coaye..........http://ideone.com/SoLkPk
2015-09-23 09:54:50 Vũ Quang Thịnh
Tổng tiền tố một cách tham lam, AC 100 :)))

Last edit: 2015-09-23 09:55:09
2015-09-14 10:45:53 Do Hong Huan
Bài nhãm, để longint AC, int64 thì 70
2015-09-05 14:23:55
duyệt trâu ac hư cấu quá
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.