GMatrix.scala

object GMatrix extends App {
  def subMaxSum(n: Int, k: Int, c: Int, x: Int, a: IndexedSeq[Int], b: IndexedSeq[Int]): Long = {
    def m(i: Int, j: Int): Int = (a(i - 1) * i + b(j - 1) * j + c) % x
    def slideMax: IndexedSeq[Int] => IndexedSeq[Int] = { xs =>
      type Q = IndexedSeq[(Int, Int)]
      @annotation.tailrec
      def enqueue(deque: Q, e: (Int, Int)): Q = deque.lastOption match {
        case Some((x, i)) if x < e._1 => enqueue(deque.init, e)
        case _ => deque :+ e
      }
      @annotation.tailrec
      def max(deque: Q, from: Int): (Int, Q) =
        if (deque.head._2 < from) max(deque.tail, from)
        else (deque.head._1, deque)

      val ys = xs.zipWithIndex
      val (acc, deque) = ((List.empty[Int], (ys take k).foldLeft[Q](Vector())(enqueue)) /: (0 until n - k)) {
        case ((acc, deque), i) =>
          val (m, deque1) = max(deque, i)
          (m :: acc, enqueue(deque1, ys(k + i)))
      }
      (max(deque, n - k)._1 :: acc).reverse.toIndexedSeq
    }
    val slided = for (i <- 1 to n) yield slideMax(for (j <- 1 to n) yield m(i, j))
    (for (j <- 0 to n - k) yield slideMax(for (i <- 0 until n) yield slided(i)(j))).flatten.map(_.toLong).sum
  }

  def process(lineIn: Iterator[String])(lineOut: String => Unit) =
    for (i <- 1 to lineIn.next().toInt) {
      def readInts() = lineIn.next().split(' ').map(_.toInt)
      val Array(n, k, c, x) = readInts()
      val a = readInts()
      val b = readInts()
      lineOut(s"Case #$i: ${subMaxSum(n, k, c, x, a, b)}")
    }

  val filename = "D-large-practice"
  val writer = new java.io.PrintWriter(filename + ".out")
  try {
    process(io.Source.fromFile(filename + ".in").getLines) { s =>
      writer.println(s); writer.flush()
    }
  } finally {
    writer.flush(); writer.close()
  }
}

GMatrixTest.scala

import org.scalatest._

import GMatrix._

class GMatrixTest extends FunSuite with Matchers {

  test("sample #1") {
    assert(subMaxSum(1, 1, 1, 5, Vector(1), Vector(1)) === 3)
  }

  test("sample #2") {
    assert(subMaxSum(2, 1, 5, 11, Vector(1, 2), Vector(3, 4)) === 19)
  }

  test("sample #3") {
     assert(subMaxSum(3, 2, 3, 109, Vector(6, 4, 3), Vector(2, 1, 5)) === 80)
  }

  test("sample case") {
    val input = """3
1 1 1 5
1
1
2 1 5 11
1 2
3 4
3 2 3 109
6 4 3
2 1 5""".lines

    val expected = """Case #1: 3
Case #2: 19
Case #3: 80""".lines

    lineComparison(input, expected)
  }

  test("full small case") {
    val input = io.Source.fromFile("D-small-practice.in").getLines()
    val expected = io.Source.fromFile("D-small-practice.out").getLines()

    lineComparison(input, expected)
  }

  test("full large case") {
    val input = io.Source.fromFile("D-large-practice.in").getLines()
    val expected = io.Source.fromFile("D-large-practice.out").getLines()

    lineComparison(input, expected)
  }

  def lineComparison(input: Iterator[String], expected: Iterator[String]) {
    process(input) { s =>
      for (line <- s.lines) assert(line.trim === expected.next().trim)
    }
    assert(expected.hasNext === false, "Finished too fast.")
  }

}