POI Plot Purchase

Правка en1, от WARush143, 2016-12-21 02:09:43

Hi,

I'm solving this POI problem: http://main.edu.pl/en/archive/oi/15/kup . Basically, given an integer k(1 ≤ k ≤ 109) and an N by N square grid(1 ≤ N ≤ 2000) of non-negative integers, you have to find some rectangle in the grid such that its sum is between k and 2k, inclusive.

I can come up with O(n3) solution using prefix sums and monotonicity, however to make the problem fit the time limit I need something faster. By google translating the editorial, I think it's divide and conquer, but I couldn't understand the details as the translation was very bad. I would appreciate any help on this problem :D

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский WARush143 2016-12-21 02:09:43 665 Initial revision (published)