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

Doubt in Codechef long MARRAYS
Автор skpro19, история, 7 лет назад, По-английски

This is the problem link. This is my submission. It is getting TLE. I read another guy's recursive approach. It got full points. I don't understand, why this code is getting accepted, but mine is not.

Any help would be really appreciated.

Peace.

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Please explain your approach.

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    dfs(level, pos) returns the maximum value possible from that level, if we use the element at 'pos' as the last element of the level.

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

You should no use recursive approach. This question can be solved in O(m1+m2+m3+....) where mi is the number of ingredients in the ith dish, you can see my code https://www.codechef.com/viewsolution/15833805 I used the logic that only maximum or minimum number in the previous dish will cause the highest quality hence check which one should be used it's kind of greedy approach.

→ Ответить