Đố vui tin học (HSG9 VT 2023)

Điểm: 1200 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 256M

Input: GIFT.inp

Output: GIFT.out

Tác giả:

Sunlight

Dạng bài

Để tổng kết phát thưởng cho cuộc thi Đố vui tin học, Ban tổ chức có $N$ phần quà được đánh thứ tự từ $1$ tới $N$ , phần quà thứ $i$ có giá trị $a_i$ . Ban tổ chức yêu cầu học sinh chọn các phần quà theo quy tắc sau:

Phần quà chọn sau phải có số thứ tự lớn hơn phần quà chọn trước đó.
Phần quà chọn sau phải có giá trị lớn hơn phần quà chọn trước đó ít nhất $K$ giá trị

Yêu cầu: Hãy giúp các bạn học sinh lựa chọn theo quy tắc ban tổ chức đặt ra sao cho số lượng phần quà được chọn là nhiều nhất

Input và Output

Input: (GIFT.inp)

Dòng đầu tiên chứa 2 số nguyên dương $N$ và $K$ cách nhau một ký tự trắng ( $N\le 10^4, K\le 10^3$ )
$N$ dòng tiếp theo, dòng thứ $i$ chứa số nguyên dương $a_i$ ( $a_i\le 10^6$ ) là giá trị của phần quà thứ $i$

Output: (GIFT.out)

Một dòng duy nhất chứa số lượng phần quà nhiều nhất thỏa mãn yêu cầu

Bonus

Bạn có thể giải bài toán này với $N\le 10^6$ ?

Subtasks

Subtask 1 $(10\%)$ : $N\le 20$ .
Subtask 2 $(30\%)$ : $N\le 10^4$ .
Subtask 3 $(30\%)$ : $N\le 10^5$ .
Subtask 4 $(30\%)$ : Không có giới hạn gì thêm.

Sample

Input (GIFT.inp)

Output (GIFT.out)

Bình luận

Không có bình luận nào.