ok so I got AC
the key difference seems to be in using correct way to read the input
if I use readLine().split(' ').map(_.toInt) then it always TLE
but if I read input using Java Scanner:
  val sc = new Scanner(System.in);
  .... sc.nextInt() ...
then it works fine

Edited by author 31.03.2014 08:45

I also have many problems with scala. My scala code runs two times slow than the corresponding java code. Sometimes it's really hard to optimize. My tips (in general, not specifically about this problem):
* don't use vars if not really necessary
* foldLeft and similar functions are slow unfortunately (although I tend to use them anyways, only switch to for when I got a TLE)
* array initialization is REALLY slow especially if you use fill (much more slower than java). try to keep your arrays as small as possible. For example sometimes it's possible to keep only the last two rows of a matrix.