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 |
|
|
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 |