Hello Codeforces, on the 1st stage of the lastest Polish Olympiad in Informatics, appeared a problem which I could not get full score for. I would be very thankful, could somebody provide me with an efficient solution.
Self-translated statement: (Różnorodność, in Polish https://szkopul.edu.pl/problemset/problem/eHGwrk9xShVF-z_2f7K4Yyb_/statement/)
You're given a 2d array of integers. Subarrays of this array, of size KxK we will call it's K-fragments. "Diversity" of a K-fragment we will call the number of different elements it contains. You are to count the max diversity of a K-fragment, out of all possible and the sum of diversities from all K-fragments of the array.
Input: First line contains 3 integers m,n,K denoting the array size (mxn) and size of fragments (KxK). m,n,K <= 3000
The next m lines has n integers being the successive numbers of the array. The numbers are in interval [1,100000].
For input: the right output is: 3 5 2 4 20 1 5 3 3 3 4 1 3 3 4 4 2 4 4 3
The memory limit is 512MB, time limit 15 seconds.
I made a solution, which traversed through every K-fragment, by erasing the first K element column of the previous fragment, and including new column of K elements.
For that I got only 64 points from a total of 100.