radical's blog

Who can help me solve this problem about GYM KTU DAY 2
By radical, history, 9 years ago, In English

The proble is here. here I have try my best to solve it.... But my method is too complex that got TLE. My code is here.

Tags gym, ktu
  • Vote: I like it
  • +6
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

It can be solve in O(n2) time per testcase if you something similar to two pointers instead of binary search. Let me explain:

At each position we try to increase the answer as much as possible (that is, as long as the 1 larger submatrix still has sum ≤ w). Now notice that the answer can only increase n times — so the whole thing is O(n2) (using prefix sums as you did).

Here's my AC code: link

→ Reply