Submission #1591139

---

Source Code Expand

N = gets.to_i
D = N.times.map do
  gets.split.map(&:to_i)
end
Q = gets.to_i
P = Q.times.map do
  Math.sqrt(gets.to_i).to_i
end

memo = []

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

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

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

  max = b.map(&:max).max
  memo[p] = max
  puts max
end

Submission Info

Judge Result