Submission #5098373


Source Code Expand

object Main {
  def main(args: Array[String]): Unit = {
    val s = new Main()
    s.solve()
    s.out.flush()
  }
}

class Main {
  import java.io._
  import java.util.StringTokenizer
  import java.util.Arrays.sort

  import scala.collection.mutable
  import math.{abs, max, min}
  import mutable.ArrayBuffer
  import scala.reflect.ClassTag

  val MOD = 1000000007
  val out = new PrintWriter(System.out)

  def solve(): Unit = {
    val N = ni()
    val A = na(N)
    val dp = Array.fill[Long](5, N + 1)(1e18.toLong)
    dp(0)(0) = 0

    // 01234
    // 02120 これの部分文字列がありえる状態って感じ
    REP(N) { i =>
      dp(0)(i + 1) = dp(0)(i) + A(i) //0 -> 0 全部取り除く必要がある

      // *注意* 1,2,3への遷移は0のときにはできない
      if (A(i) != 0) {
        dp(1)(i + 1) = reduceDimFlip(dp, i, 2)(min)+ A(i) % 2 // 0, 1 -> 1 奇数の場合は1こ取り除く
        dp(2)(i + 1) = reduceDimFlip(dp, i, 3)(min) + ((A(i)%2)^1) // 0, 1, 2 -> 2 偶数の場合は1こ取り除く
        dp(3)(i + 1) = reduceDimFlip(dp, i, 4)(min) + A(i) % 2 // 0, 1, 2, 3 -> 3 奇数の場合は1こ取り除く
      }
      dp(4)(i + 1) = reduceDimFlip(dp, i, 5)(min) + A(i)  //0, 1, 2, 3, 4 -> 4 全部取り除く必要がある
    }

    debugDimFlip(dp)

    val ans = dp.map(_(N)).min
    out.println(ans)
  }

  private val oj = System.getenv("ATCODER_DEBUG") == null

  def DEBUG(f: => Unit): Unit = {
    if (!oj){ f }
  }

  def debug(as: Array[Boolean]): Unit = DEBUG {
    debug(as.map(x => if(x) "1" else "0").mkString)
  }

  def debug(as: Array[Int]): Unit = DEBUG {
    debug(as.mkString(" "))
  }

  def debug(as: Array[Long]): Unit = DEBUG {
    debug(as.mkString(" "))
  }

  def debugDim(m: Array[Array[Long]]): Unit = DEBUG {
    REP(m.length) { i =>
      debug(m(i))
    }
  }

  def debugDimFlip(m: Array[Array[Long]]): Unit = DEBUG {
    REP(m(0).length) { j =>
      REP(m.length) { i =>
        System.err.print(m(i)(j))
        System.err.print(" ")
      }
      System.err.println()
    }
  }

  def debug(s: => String): Unit = DEBUG {
    System.err.println(s)
  }

  def debugL(num: => Long): Unit = DEBUG {
    System.err.println(num)
  }

  class InputReader(val stream: InputStream) {
    private val reader = new BufferedReader(new InputStreamReader(stream), 32768)
    private var tokenizer: StringTokenizer = _

    def next(): String = {
      while (tokenizer == null || !tokenizer.hasMoreTokens)
        tokenizer = new StringTokenizer(reader.readLine)
      tokenizer.nextToken
    }

    def nextInt(): Int = next().toInt
    def nextLong(): Long = next().toLong
    def nextChar(): Char = next().charAt(0)
  }
  val sc = new InputReader(System.in)
  def ni(): Int = sc.nextInt()
  def nl(): Long = sc.nextLong()
  def nc(): Char = sc.nextChar()
  def ns(): String = sc.next()
  def ns(n: Int): Array[Char] = ns().toCharArray
  def na(n: Int, offset: Int = 0): Array[Int] = map(n)(_ => ni() + offset)
  def na2(n: Int, offset: Int = 0): (Array[Int], Array[Int]) = {
    val A1, A2 = Array.ofDim[Int](n)
    REP(n) { i =>
      A1(i) = ni() + offset
      A2(i) = ni() + offset
    }
    (A1, A2)
  }
  def nm(n: Int, m: Int): Array[Array[Int]] = {
    val A = Array.ofDim[Int](n, m)
    REP(n) { i =>
      REP(m) { j =>
        A(i)(j) = ni()
      }
    }
    A
  }
  def nal(n: Int): Array[Long] = map(n)(_ => nl())
  def nm_c(n: Int, m: Int): Array[Array[Char]] = map(n) (_ => ns(m))
  def REP(n: Int, offset: Int = 0)(f: Int => Unit): Unit = {
    var i = offset
    val N = n + offset
    while(i < N) { f(i); i += 1 }
  }
  def REP_r(n: Int, offset: Int = 0)(f: Int => Unit): Unit = {
    var i = n - 1 + offset
    while(i >= offset) { f(i); i -= 1 }
  }
  def TO(from: Int, to: Int)(f: Int => Unit): Unit = {
    REP(to - from + 1, from) { i =>
      f(i)
    }
  }

  def map[@specialized A: ClassTag](n: Int, offset: Int = 0)(f: Int => A): Array[A] = {
    val res = Array.ofDim[A](n)
    REP(n)(i => res(i) = f(i + offset))
    res
  }


  def sumL(as: Array[Int]): Long = {
    var s = 0L
    REP(as.length)(i => s += as(i))
    s
  }

  def cumSum(as: Array[Int]) = {
    val cum = Array.ofDim[Long](as.length + 1)
    REP(as.length) { i =>
      cum(i + 1) = cum(i) + as(i)
    }
    cum
  }

  /**
    * 2次元配列(i, j)のjを固定してiでreduceする
    */
  def reduceDimFlip(as: Array[Array[Long]], j: Int, len: Int)(f: (Long, Long) => Long): Long = {
    var res = as(0)(j)
    REP(len - 1, 1) { i =>
      res = f(res, as(i)(j))
    }
    res
  }
}

Submission Info

Submission Time
Task D - Ears
User yakamoto
Language Scala (2.11.7)
Score 0
Code Size 4748 Byte
Status WA
Exec Time 748 ms
Memory 58176 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 600
Status
AC × 3
AC × 26
WA × 19
Set Name Test Cases
Sample s1.txt, s2.txt, s3.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt AC 686 ms 56108 KB
02.txt AC 664 ms 55716 KB
03.txt AC 661 ms 56276 KB
04.txt AC 661 ms 55520 KB
05.txt WA 610 ms 54452 KB
06.txt WA 621 ms 54256 KB
07.txt WA 701 ms 56252 KB
08.txt WA 613 ms 54088 KB
09.txt WA 595 ms 52236 KB
10.txt WA 618 ms 56276 KB
11.txt WA 593 ms 54140 KB
12.txt WA 612 ms 53864 KB
13.txt WA 717 ms 53540 KB
14.txt WA 748 ms 58176 KB
15.txt WA 595 ms 52028 KB
16.txt WA 677 ms 57276 KB
17.txt AC 602 ms 45324 KB
18.txt AC 580 ms 44580 KB
19.txt WA 594 ms 43688 KB
20.txt WA 601 ms 43256 KB
21.txt AC 556 ms 43976 KB
22.txt AC 564 ms 45416 KB
23.txt AC 613 ms 54348 KB
24.txt AC 614 ms 54168 KB
25.txt AC 626 ms 54124 KB
26.txt AC 678 ms 55644 KB
27.txt AC 597 ms 53568 KB
28.txt AC 610 ms 56084 KB
29.txt WA 591 ms 52024 KB
30.txt WA 594 ms 54180 KB
31.txt WA 587 ms 47272 KB
32.txt WA 602 ms 54324 KB
33.txt AC 579 ms 44996 KB
34.txt AC 568 ms 45288 KB
35.txt WA 580 ms 44988 KB
36.txt AC 582 ms 45972 KB
37.txt AC 327 ms 23360 KB
38.txt AC 319 ms 25280 KB
39.txt AC 324 ms 23492 KB
40.txt AC 331 ms 25408 KB
41.txt AC 326 ms 25416 KB
42.txt AC 328 ms 25280 KB
s1.txt AC 325 ms 25240 KB
s2.txt AC 325 ms 25284 KB
s3.txt AC 323 ms 25284 KB