Submission #1591219

---

Source Code Expand

require "pp"
N = gets.to_i
D = N.times.map do
  gets.split.map(&:to_i)
end
Q = gets.to_i
P = Q.times.map do
  gets.to_i
end

memo = []
memo2 = {}

P.each do |p|
  if memo[p]
    puts memo[p]
    next
  end

  pairs = (1..p).select { |i| p / i <= N && i <= N }.map do |n|
    [[n, p / n], [p / n, n]]
  end.flatten(1)

  pairs.each do |p1, p2|
    if memo2[[p1, p2]]
      next
    end

    # 行方向の圧縮
    a = Array.new(N) do
      Array.new(N - p1 + 1, 0)
    end
    N.times do |i|
      a[i][0] = D[i][0, p1].inject(:+)
      (N - p1).times do |j|
        a[i][j + 1] = a[i][j] + D[i][j + p1] - D[i][j]
      end
    end

    # 列方向の圧縮
    b = Array.new(N) do
      Array.new(N, 0)
    end
    (N - p1 + 1).times do |i|
      b[0][i] = a[0, p2].map { |c| c[i] }.inject(:+)
      (N - p2).times do |j|
        b[j + 1][i] = b[j][i] + a[j + p2][i] - a[j][i]
      end
    end
    max = b.map(&:max).max
    memo2[[p1, p2]] = max
  end

  p pairs.map { |i| memo2[i] }.max
end

Submission Info

Judge Result