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

VOLIS - Dãy con không giảm 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/volis


Cho 1 dãy số nguyên a[1], a[2], …, a[N]. Bạn có thể cộng hoặc trừ mỗi phần tử đi một lượng tối đa là D (dãy số sau khi cộng/trừ có thể xuất hiện số âm hoặc số thực). Hãy tìm độ dài của dây con không giảm dài nhất của dãy số, nếu cộng/trừ các phân tử một cách tối ưu.

Lưu ý: dãy con của dãy số là dãy số a[x[1]], a[x[2]], ..., a[x[k]] (k là một số nguyên) sao cho 1 ≤ x[1] < x[2] < ... < x[k] ≤ N.

Input

  • Dòng đầu tiên chứa 2 số nguyên N và D.
  • Dòng thứ 2 chứa N số nguyên a[1], a[2], …, a[N], các số được cách nhau bởi ít nhất 1 dấu cách.

 

Output

  • Một dòng duy nhất là độ dài dãy con không giảm dài nhất trong phương án tối ưu.

Giới hạn

  • 0 < N ≤ 1000.
  • 0 ≤ D ≤ 10^9.
  • 0 ≤ a[i] ≤ 10^9.
  • Trong 30% số test, D = 0.

Example

Input:

4 1 6 4 3 2 Output:

3

Giải thích: Có thể biến đổi dãy thành 6 3 3 3.


Được gửi lên bởi:VOJ Team
Ngày:2011-12-23
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C C++ 4.3.2 CPP PAS-GPC PAS-FPC
Nguồn bài:Nguyễn Vương Linh

hide comments
2020-08-22 16:22:07
bài ez
2017-12-29 10:51:55
qvluom 1 hit AC =))))
2017-11-16 10:48:46
trau cung ac :))))
2017-11-16 09:27:47
nhật hào sạch
2017-11-11 10:24:12
DP O(N^2) 1 đấm AC
frostpixel aka.How 2 AC
2017-11-10 13:23:56
đéo hiểu sao đc có 60
2017-08-03 18:11:05
http://cowboycoder.tech/spoj/spojvolis-day-con-khong-giam-dai-nhat
2017-07-05 09:52:05
Bài này dùng luồng, còn phải xử lý cây + HLD + interval Tree, AVL với suffix array nữa :(
2017-06-06 09:19:49
Cac ban oi, sol O(n) choi trau nhe!
2016-10-22 18:12:08
=))))
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.