gMatrix.scala

package Main

import java.io.FileInputStream

import scala.annotation.tailrec
import scala.collection.immutable.IndexedSeq
import scala.io.StdIn


object Main extends App {
//  Console.setIn(new FileInputStream("example.in"))

  Console.setIn(new FileInputStream("D-small-practice.in"))
  Console.setOut(new FileOutputStream("D-small-practice.out"))

//  Console.setIn(new FileInputStream("D-large-practice.in"))
//  Console.setOut(new FileOutputStream("D-large-practice.out"))

  def binarySearch(ds: Vector[Long], key:Long):Int = {
    @tailrec
    def go(lo:Int, hi:Int):Int = {
      if (lo > hi) {
        lo
      } else {
        val mid = lo + (hi + lo)  / 2
        ds(mid) match {
          case mv if (mv == key) => mid
          case mv if (mv <= key) => go(mid + 1, hi)
          case _ => go(lo, mid - 1)
        }
      }
    }
    go(0, ds.size - 1)
  }

  def solve(n : Long, k : Long, c : Long, x : Long, a : Array[Long], b : Array[Long]): Long = {
    def getElement(i : Long, j : Long) : Long = ( a((i.toInt-1) % a.length) * i + b((j.toInt-1) % b.length) * j + c ) % x


    def getMax(size:Long, count:Long, getElement:(Long, Long) => Long): IndexedSeq[List[Long]] =
      (1L to count).map { i =>
        val init = (1L to size).map { j => getElement(i, j) }.toVector
        val result = ((init, List[Long]()) /: (0L to (n - size)))((acc, x) => {

          val element: Long = getElement(i, x + size + 1)
          val value: Vector[Long] = acc._1.tail :+ element

          val updateIdx = acc._3.indexOf(acc._1.head)
          (value, acc._2.max+: acc._2)
        })
        result._2.reverse
    }

    val Hmax = getMax(k, a.length, getElement)

    val maxList = getMax(k, a.length - (k - 1), (i: Long, j:Long) => {
      val sub = Hmax((j.toInt - 1) % Hmax.length)
      sub((i.toInt - 1) % sub.length)
    })
    maxList.flatten.sum
  }

  val cases = StdIn.readLine().toInt
  (1 to cases) foreach { i => {
    val Array(n, k, c, x) = StdIn.readLine().split(' ').map(_.toLong)
    val a = StdIn.readLine().split(' ').map(_.toLong)
    val b = StdIn.readLine().split(' ').map(_.toLong)

    println(s"Case #$i: ${solve(n, k, c, x, a, b)}")
  }}
}