Блог пользователя 1Codeforces

SPOJ SALES
Автор 1Codeforces, 11 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
11 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

you should think a better solution

→ Ответить
»
11 лет назад, # |
← Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

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)

→ Ответить