reclusion's blog

How can I improve CF364 Div2B
By reclusion, history, 8 years ago, In English

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://codeforces.com/contest/701/submission/19371051

  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
8 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

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)

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply