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

WA????
Автор lusho, история, 7 лет назад, По-английски

Why this code is giving me WA in 811C - Владик и запоминающаяся поездка, i used DP the tipical take or not take:

here is my code: 27467986

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

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

Consider lines 57-58:

if(Ini[V[i]]==i)
  Sum[i]=SubArray(Ini[V[i]],Fin[V[i]]);

You then use this Sum array in lines 40-41:

if(Ini[V[k]]==k)
  first=Sum[k]+Solve(Fin[V[k]]+1);

The problem is that in the Sum array you're considering the xor-sum of a subarray from the first occurrence of a number to its last. However, within this subarray, there may occur other numbers, whose first occurrence is before the beginning or whose last occurrence is after the end. This would make taking such a subarray into the solution illegal. You're not considering this, which is why your answer comes out to be greater than the judge's solution.

→ Ответить