BoxFactory.scala

import scala.collection.mutable

object Main {

  case class Item(count:Long, typeName:Long)


  def solve(box:List[Item], toy:List[Item]): Long = {

    var cache = mutable.HashMap[(List[Item], List[Item]), Long]()

    def subSolve(box:List[Item], toy:List[Item], depth:Int):Long = {
      var ret = 0L
      if (box.isEmpty || toy.isEmpty) {
        ret = 0
      } else if (cache.exists(n => n._1 ==(box, toy))) {
        ret = cache.apply((box, toy))
      } else if (box.head.typeName == toy.head.typeName) {
        val currentBox = box.head
        val currentToy = toy.head
        val boxedItemCount = Math.min(currentBox.count,currentToy.count)
        ret = boxedItemCount +
          (currentBox.count - currentToy.count match {
            case a if a > 0 => subSolve(currentBox.copy(count = currentBox.count - boxedItemCount) :: box.tail, toy.tail, depth + 1)
            case a if a < 0 => subSolve(box.tail, currentToy.copy(count = currentToy.count - boxedItemCount) :: toy.tail, depth + 1)
            case _ => subSolve(box.tail, toy.tail, depth + 1)
          })
      } else {
        ret = Math.max(
          subSolve(box.tail, toy, depth + 1),
          subSolve(box, toy.tail, depth + 1)
        )
      }
      cache += ((box, toy) -> ret)
      ret
    }
    subSolve(box.reverse, toy.reverse, 0)
  }

  def main(args: Array[String]) {

    val writer = new java.io.PrintWriter("c-large.out")
    try {
      process(io.Source.fromFile("C-large-practice.in").getLines)(writer.println)
    } finally {
      writer.flush()
      writer.close()
    }
  }

  def process(lineIn: Iterator[String])(lineOut: String => Unit) = {

    for (i <- 1 to lineIn.next().toInt) {
      lineIn.next()
      println(i)
      val boxLine = lineIn.next().split(" ").map(_.toLong)
      val box = for ( n <- (0 until boxLine.length) by 2) yield Item(boxLine(n), boxLine(n + 1))
      val toyLine = lineIn.next().split(" ").map(_.toLong)
      val toy = for ( n <- (0 until toyLine.length) by 2) yield Item(toyLine(n), toyLine(n + 1))

      lineOut(s"Case #$i: ${solve(box.toList, toy.toList)}")
    }
  }
}