challenge — higher limits

Revision en1, by Radewoosh, 2016-08-21 18:21:50

Hi guys!

On IOI I've learned many new things, so now I want to give you a challenge. You probably remember my and Errichto's eliminations to VK Cup 2016. Let's focus on this problem: 674C - Levels and Regions

Main solution was solving it in O(n*k), because k wasn't greater than 50. What if k is just lower or equal to n? :D

I'm waiting for your ideas.

Tags after ioi, challenge, dp, convex hull optimization, complexity optimization

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English Radewoosh 2016-08-22 01:12:03 2 Tiny change: 'es(i)-res(r-1)$.\n\nT' -
en4 English Radewoosh 2016-08-21 19:51:28 7 Tiny change: 'n? :D\n\n\n\n\n 'n? :D\n\n\\\n\n\n
en3 English Radewoosh 2016-08-21 19:48:43 305 Tiny change: ' n? :D\n\nI'm posting solution below.\n\n\n ' n? :D\n\n\n\n\n
en2 English Radewoosh 2016-08-21 19:41:55 1505 Tiny change: 'n below that text, if ' -
en1 English Radewoosh 2016-08-21 18:21:50 393 Initial revision (published)