Getting TLE on CF Round#426 (div-1) B

Правка en1, от arman_ferdous, 2017-08-16 22:05:20

The problem link : 833B - Кондитерская My TLE solution : 29511490

Definition of dp state: dp[s][p] means the maximum total value we can get from the p-th part by putting some amount of boxes starting from s.

And to calculate the number of distinct integers in a range I used a persistent segment tree. First I stored the previous occurance for each number. Then for any interval i to j I only need to see how many numbers in previous[i...j] are less than i. And that is where the persistent seg tree helped me.

So if I am not wrong then at the worst case the dp table will be fully filled so the complexity for the solve() function would be O(n*k*distinct_int_query) in this case it is O(n*k*log n). Building the segment tree at first will take O(n*log n). Afterwards updating for each element will take a total of O(n*log n)

So total complexity would be O(n*k*log n) right? Then why doesn't it pass? Why TLE???

P.S: Most likely I am wrong. So plz tell how to do the wrong thing right.

Теги dynamic programming, persistent segment tree, #tle, #help

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский arman_ferdous 2017-08-16 22:05:20 1049 Initial revision (published)