Submission #5098758
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, 3の遷移のとき、0の場合は最低2必要ってのに注意。2のときは最低1必要
dp(1)(i + 1) = reduceDimFlip(dp, i, 2)(min) + (if (A(i) == 0) 2 else A(i)%2) // 0, 1 -> 1 奇数の場合は1こ取り除く
dp(2)(i + 1) = reduceDimFlip(dp, i, 3)(min) + (if (A(i) == 0) 1 else A(i)%2^1) // 0, 1, 2 -> 2 偶数の場合は1こ取り除く
dp(3)(i + 1) = reduceDimFlip(dp, i, 4)(min) + (if (A(i) == 0) 2 else 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 |
600 |
Code Size |
4815 Byte |
Status |
AC |
Exec Time |
731 ms |
Memory |
57904 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
600 / 600 |
Status |
|
|
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 |
687 ms |
56280 KB |
02.txt |
AC |
684 ms |
55640 KB |
03.txt |
AC |
678 ms |
55588 KB |
04.txt |
AC |
681 ms |
55940 KB |
05.txt |
AC |
731 ms |
55996 KB |
06.txt |
AC |
630 ms |
54424 KB |
07.txt |
AC |
721 ms |
57904 KB |
08.txt |
AC |
636 ms |
53912 KB |
09.txt |
AC |
637 ms |
53896 KB |
10.txt |
AC |
637 ms |
56104 KB |
11.txt |
AC |
721 ms |
55956 KB |
12.txt |
AC |
641 ms |
55892 KB |
13.txt |
AC |
625 ms |
54280 KB |
14.txt |
AC |
638 ms |
54372 KB |
15.txt |
AC |
639 ms |
54516 KB |
16.txt |
AC |
640 ms |
54332 KB |
17.txt |
AC |
640 ms |
56000 KB |
18.txt |
AC |
685 ms |
54884 KB |
19.txt |
AC |
678 ms |
54124 KB |
20.txt |
AC |
696 ms |
56024 KB |
21.txt |
AC |
621 ms |
54248 KB |
22.txt |
AC |
631 ms |
53836 KB |
23.txt |
AC |
621 ms |
54292 KB |
24.txt |
AC |
639 ms |
56200 KB |
25.txt |
AC |
642 ms |
56332 KB |
26.txt |
AC |
682 ms |
55712 KB |
27.txt |
AC |
640 ms |
54196 KB |
28.txt |
AC |
612 ms |
53712 KB |
29.txt |
AC |
617 ms |
54088 KB |
30.txt |
AC |
616 ms |
54264 KB |
31.txt |
AC |
626 ms |
56148 KB |
32.txt |
AC |
625 ms |
54020 KB |
33.txt |
AC |
698 ms |
55676 KB |
34.txt |
AC |
638 ms |
54244 KB |
35.txt |
AC |
718 ms |
57176 KB |
36.txt |
AC |
634 ms |
54432 KB |
37.txt |
AC |
333 ms |
25124 KB |
38.txt |
AC |
337 ms |
25396 KB |
39.txt |
AC |
330 ms |
25020 KB |
40.txt |
AC |
334 ms |
25392 KB |
41.txt |
AC |
344 ms |
25284 KB |
42.txt |
AC |
332 ms |
23496 KB |
s1.txt |
AC |
332 ms |
25284 KB |
s2.txt |
AC |
332 ms |
25300 KB |
s3.txt |
AC |
337 ms |
25408 KB |