Решаю задачку 2004 года с ограничениями MAXK <= 2000 MAXN <= 20000

Умею решать её за O( MAXK * MAXN )

Зашла бы такая асимптотика в 2004? И умеете ли вы ее решать быстрее?

Задача IOI 2004 Гермес. https://yadi.sk/i/oF7CX1tEaSsSX