Why's my CHT so Slow?

Правка en2, от minimario, 2017-09-25 05:34:57

Hi all,

I was solving this problem: Link. It's fairly easy, so if you don't really want to solve it, I'll go ahead and write the dp recurrence here:

dp[i][k] = max(dp[j][k - 1] + p[j] * (p[i] - p[j]))

A pretty obvious CHT problem. But I'm getting TLE on the last test case. I opened some AC codes, and I didn't see much difference between our codes, so I'm wondering what makes mine so slow and the other one so fast!

436 ms code

My submission

If anyone has some insights, please comment (or PM me) with details!

(P.S.: If anyone has a fairly fast implementation of CHT that would like to challenge the 436 ms, go ahead and submit it :))

Thanks so much,

-minimario

Теги cht, optimization, apio

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский minimario 2017-09-25 05:52:54 34 Tiny change: ' obvious CHT problem. ' -> ' obvious Convex Hull Trick (CHT) problem. '
en2 Английский minimario 2017-09-25 05:34:57 180
en1 Английский minimario 2017-09-25 05:34:16 657 Initial revision (published)