A wildlife reserve has installed n trail cameras in a single line along a ridge trail, numbered 1 to n in the order they stand on the trail. On a given day, camera i recorded one activity reading a_i (a positive integer). Ecologists want to examine one contiguous block of exactly k consecutive cameras.
A block is called biodiverse if it contains at least m distinct reading values among its k readings (a value that repeats within the block still counts only once toward this distinct total). Among all biodiverse blocks of exactly k consecutive cameras, find the maximum possible sum of the readings in the block. If no block of k consecutive cameras is biodiverse, report 0.
Line 1: three integers n m k. Line 2: n integers a_1 a_2 ... a_n, the reading recorded by camera i.
A single integer: the maximum sum of readings over all biodiverse blocks of exactly k consecutive cameras, or 0 if no such block exists.
Example 1
Input
6 3 4 2 6 7 3 1 7
Expected
18
Explanation
The block of cameras 1-4, readings [2,6,7,3], has 4 distinct values (at least the required 3) and sums to 18. Checking every other length-4 block, none is both biodiverse and higher-summing, so 18 is the answer.
Example 2
Input
7 1 3 5 9 9 2 4 5 4
Expected
23
Explanation
With m = 1, every length-3 block is automatically biodiverse (it always has at least 1 distinct value), so the answer is simply the maximum sum over all length-3 blocks. The block of cameras 1-3, readings [5,9,9], sums to 23, the largest sum among all length-3 blocks.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →