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

Автор reclusion, история, 8 лет назад, По-английски

Here's my code : http://pastebin.com/WPfr9ZX4

Initially all columns and rows have N items each. After item is placed on the grid I subtract 1 from all the columns and rows and update the result accordingly. On test 7 I get TLE. How can I make this faster?

My submission : http://mirror.codeforces.com/contest/701/submission/19371051

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

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

Your code works O(M*N). Therefore, in worst case your program makes 10^10 operations. Obviously, TLE happens. Try to think about more optimal solution. Hint: optimal solution should work O(N + M)

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

Note that if there are r rows without rook and c columns without rook, there would be exactly r × c cells not under attack.