TRAKA — TRAKA SPOJ

Revision en1, by So_Cold, 2016-08-30 10:12:43

here is the problem
it's really an interesting problem but just a few people have solved it
I came up with o(n^2 * log2(2)) solution (using dp and segment tree)
it could pass only 40% of test cases
someone told me it could be solved using convex hull trick
so please explain your solution
thanks in advance

the problem
Tags convexhull, help

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English So_Cold 2016-08-31 16:32:05 5 Tiny change: '^2 * log2(2)) solutio' -> '^2 * log2(n)) solutio'
en1 English So_Cold 2016-08-30 10:12:43 1951 Initial revision (published)