Submission #1591148

---

Source Code Expand

require 'pp'
N = gets.to_i
MAP = [nil] + N.times.map{ [nil] + gets.split.map(&:to_i) }
Q, *PS = readlines.map(&:to_i)

scores = Array.new(N*N + 1, 0)
sums = {}

N.downto(1) do |y1|
  N.downto(1) do |x1|
    y1.upto(N) do |y2|
      x1.upto(N) do |x2|
        sum = MAP[y1][x1]
        sum += sums[y1][x1+1][y2][x2] unless x1==x2
        sum += sums[y1+1][x1][y2][x1] unless y1==y2
        sums[y1] ||= {}
        sums[y1][x1] ||= {}
        sums[y1][x1][y2] ||= {}
        sums[y1][x1][y2][x2] = sum
        area = (x2-x1+1)*(y2-y1+1)
        scores[area] = sum if scores[area] < sum
      end
    end
  end
end

2.upto(N*N) do |i|
  scores[i] = scores[i-1] if scores[i] < scores[i-1]
end

PS.each do |pn|
  p scores[pn]
end

Submission Info

Judge Result