oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

toiletbreaks Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

statement.html

Problem Statement

Some NUSH students are taking part in an Informatics Olympiad test.

During the test, Mr Li received N requests from students to go to the toilet. He wants to encourage students to go to the toilet so that they can make magical observations due to the observation fairy in the toilet. However, in light of recent happenings, he is worried that students may be cheating by leaving hints to questions in the toilet.

To prevent cheating, he has assigned an ability level to all students who requested to go to the toilet. The ith student has ability Ai. He will only allow a student to go to the toilet if his ability is at least K higher than all previous students who went to the toilet.

The test is over, and Mr Li is wondering about the maximum number of students who could have gone to the toilet if he had approved their requests optimally. Can you tell him how many students could have gone to the toilet?

Input

The first line of input contains two integers, N and K.

The second line of input contains N integers, representing the array A.

Output

The first and only line of output should contain a single integer, denoting the maximum number of students who could have gone to the toilet.

Limits

For all subtasks, 1 ≤ N ≤ 5000 and 0 ≤ K, Ai ≤ 109.

Subtask 1 (20%): K = 0 or 1

Subtask 2 (31%): N ≤ 5

Subtask 3 (49%): N ≤ 5000

Subtask 4 (0%): Sample test cases.

Sample Input 1

6 4
1 5 6 9 10 13

Sample Output 1

4

Sample Input 2

9 1
1 1 2 3 5 8 13 21 34 

Sample Output 2

8

Explanation

For the first sample test case, allowing person 1, 2, 4 and 6 to go to the toilet is optimal. For the second sample test case, allowing everyone except person 1 to go to the toilet is optimal.

Tags

Dynamic Programming

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
120131s256MBMinimum
231131s256MBMinimum
349351s256MBMinimum
4021s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o toiletbreaks -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.