ICPC Domestic 2003 Get Many Persimmon Trees

aoj-icpc-1125.rb

# ICPC Domestic 2003
# Get Many Persimmon Trees
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1125
def cumsum2d(m)
  h = m.size-1
  w = m[0].size-1
  ms = Array.new(h+1){Array.new(w+1, 0)}
  (h+1).times do |i|
    w.times do |j|
      ms[i][j+1] = ms[i][j] + m[i][j+1]
    end
  end
  (w+1).times do |j|
    h.times do |i|
      ms[i+1][j] = ms[i][j] + ms[i+1][j]
    end
  end
  return ms
end

def get2dsum(m, x, y, w, h)
  return m[y-1+h][x-1+w] - m[y-1][x-1+w] - m[y-1+h][x-1] + m[y-1][x-1]
end

while true
  n = gets.chomp.to_i
  break if n == 0
  w, h = gets.chomp.split(" ").map(&:to_i)
  m = Array.new(h+1){Array.new(w+1, 0)}
  n.times do
    x, y = gets.chomp.split(" ").map(&:to_i)
    m[y][x] = 1
  end
  ms = cumsum2d(m)
  ret = 0
  s, t = gets.chomp.split(" ").map(&:to_i)
  (1..(h-t+1)).each do |i|
    (1..(w-s+1)).each do |j|
      ret = [ret, get2dsum(ms, j, i, s, t)].max
    end
  end
  puts ret
end