Mock CCO '18 Contest 4 Problem 6 - Splitting Drones

View as PDF

Submit solution

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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.