Mock CCO '18 Contest 4 Problem 6 - Splitting Drones

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 0.5s
Memory limit: 64M

Problem type

As we know, the art of splitting workers to separate mineral patches is a tricky one.

There are N mineral patches in order, each has A_i minerals to be mined. Our StarCraft player will split L drones to mine L contiguous mineral patches.

The StarCraft player notes that for some values of L, over the N-L+1 ways to send drones to mine minerals, the sequence of values corresponding to the mineral patches being mined is the same.

The StarCraft players wishes to find the maximum L such that some sequence of length L appears at least K times among the possible sequences of values that can be mined.

Constraints

1 \le N \le 20 \cdot 10^3

2 \le K \le N

0 \le A_i \le 10^6

Input Specification

The first line will contain two space-separated integers, N and K.

Each of the next N lines contains an integer, the A_i in order.

Output Specification

Output the maximum L. The input data guarantee that L is positive.

Sample Input

8 2
1
2
3
2
3
2
3
1

Sample Output

4

Comments

There are no comments at the moment.