All Tracks Algorithms Dynamic Programming Introduction to Dynamic Programming 1 Problem

Flat Earth Society
Tag(s):
No tags
Problem
Editorial
Analytics

Abhishek Sinha like everyone else was a firm believer of Sphere Earth, believing what school has taught and not trusting their own insights.
Once Sir Notsocool Hawkins quoted "Everything in life doesn't need to be hard and complex, sometimes it is simple and flat, just like our Planet".

After getting motivated, Abhishek Sinha establishes 'Flat Earth Society' and to join the society, one must solve the following problem:

Given an array A consisting of N integers. In a single step player can choose an element of the array (let's denote it ak) and delete it, at that all elements equal to ak + 1,ak + 2......ak + R and ak - 1,ak - 2.....ak - L also must be deleted from the array. This step will add ak points to player. Player can perform any number of steps.

Find maximum points which can be obtained.

 

Input Format

First line contains T testcases.

Each Testcase contains three integers N, and R, where N is number of elements in array, and use of L and R has been explained in Problem statement.

The next line contains N integers denoting elements of array A.

Output Format

A single line for each test case, output a single integer denoting the maximum points possible..

Constraints

1 <= T <= 100

1 <= N, L, R <= 10^5

1<= ak <=10^5

SAMPLE INPUT
1
9 1 1
1 2 1 3 2 2 2 2 3
SAMPLE OUTPUT
10
Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, R(RScript), Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

BIT Mesra

Challenge Name

CodeZilla Prelims

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?