Help needed with recent problem from POI

Правка en1, от Linkus, 2018-01-03 18:36:15

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].

Example:

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, thus the complexity of my answer was O(k*(n-1)*(m-1)) ~ O(k*n*m)

For that I got only 64 points from a total of 100.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Linkus 2018-01-03 18:41:07 67
en1 Английский Linkus 2018-01-03 18:36:15 1445 Initial revision (published)