Submission #147911

---

Source Code Expand

import java.util.Scanner

/**
 * Created by hama_du on 2014/03/22.
 */
object Main extends App {
  val in = new Scanner(System.in)
  val N = in.nextInt()
  val D = (0 until N).map(_ => {
    (0 until N).map(_ => in.nextInt()).toArray
  }).toArray

  val imos = buildImos(D)
  val map = buildMap(imos)

  val Q = in.nextInt()
  (0 until Q).foreach(_ => {
    val P = in.nextInt()
    println(map(P+1))
  })


  def buildImos(a: Array[Array[Int]]): Array[Array[Int]] = {
    val ret = Array.ofDim[Int](a.length+1, a(0).length+1)
    for (i <- 0 until a.length) {
      for (j <- 0 until a(0).length) {
        ret(i+1)(j+1) = (ret(i)(j+1) + ret(i+1)(j) - ret(i)(j)) + a(i)(j)
      }
    }
    ret
  }

  def buildMap(a: Array[Array[Int]]): Array[Int] = {
    val n = a.length-1
    val m = a(0).length-1
    val best = new Array[Int](n*m+1)
    for {
      i <- 0 to n
      j <- 0 to m
      k <- 1 to n
      l <- 1 to m
    } {
      if (i+k <= n && j+l <= m) {
        val S = k * l
        val score = a(i+k)(j+l) - a(i)(j+l) - a(i+k)(j) + a(i)(j)
        best(S) = best(S) max score
      }
    }
    best.scanLeft(0)((a, b) => a max b)
  }
}

Submission Info

Judge Result