1Codeforces's blog

SPOJ SALES
By 1Codeforces, 11 years ago, In English

This is my first blog on SPOJ.

In this problem, I am getting Time Limit Exceeded.

My code is here

Can anyone suggest a better solution? Any help will be well appreciated.

Thanks in advance.

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

ofcourse doing dp knapsack on each query will give Time limit exceeded with this contrains.

you should think a better solution

→ Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

You can initialize segment tree with knapsack DP for each segment — O(N * log(N) * B). Then you can answer single query in O(log(N) * B^2). Each vertex of segment tree contains a vector p of length B + 1. p[i] is a maximal profit you can get for i dollars using only cards from corresponding subsegment. To combine two segments a and b run for i in 0..B for j int 0..B-i c[i + j] = max(c[i + j], a[i] + b[j]); Total O(N * log(N) * B + D * log(N) * B^2)

→ Reply