Submission #2207868

---

Source Code Expand

N = gets.to_i
yakiki = Array.new(N)
for i in 0..N-1 do
  d = gets.split(" ").map { |item| item.to_i }
  yakiki[i] = d
end

# 以下解説通り

migisita = Array.new(N+1) { Array.new(N+1) {0} } #右下までの長方形内部の合計値
for i in 1..N do
  for j in 1..N do
    if i == 1 && j == 1
      migisita[N-i][N-j] = yakiki[N-1][N-1]
    elsif j == 1
      migisita[N-i][N-j] = migisita[N-i+1][N-1] + yakiki[N-i][N-j]
    elsif i == 1
      migisita[N-i][N-j] = migisita[N-i][N-j+1] + yakiki[N-i][N-j]
    else
      migisita[N-i][N-j] = migisita[N-i][N-j+1] + migisita[N-i+1][N-j] - migisita[N-i+1][N-j+1] + yakiki[N-i][N-j]
    end
  end
end

tyoho = Array.new(N+1) { Array.new(N+1) {0} } #右下までの長方形の面積
for i in 1..N do
  for j in 1..N do
    if j == 1
      tyoho[N-i][N-j] = i
    elsif i == 1
      tyoho[N-i][N-j] = j
    else
      tyoho[N-i][N-j] = tyoho[N-i][N-j+1] + tyoho[N-i+1][N-j] - tyoho[N-i+1][N-j+1] + 1
    end
  end
end

oisisa = Array.new(N**2){0}

for a in 0..N-1 do #始点y
  for b in 0..N-1 do #始点x
    for c in 0..N-1 do #終点y
      for d in 0..N-1 do #終点x
        menseki = tyoho[a][b] - tyoho[c+1][b] - tyoho[a][d+1] + tyoho[c+1][d+1]
        gokei = migisita[a][b] - migisita[c+1][b] - migisita[a][d+1] + migisita[c+1][d+1]
        if oisisa[menseki-1] < gokei
          oisisa[menseki-1] = gokei
        end
      end
    end
  end
end

for i in 1..N**2-1 do
  if oisisa[i] < oisisa[i-1]
    oisisa[i] = oisisa[i-1]
  end
end

Q = gets.to_i
tenin = []
for i in 0..Q-1 do
  pi = gets.to_i
  tenin[i] = pi
end

for i in 0..Q-1 do
  puts oisisa[tenin[i]-1]
end

Submission Info

Judge Result