結果
問題 | No.1780 [Cherry Anniversary] 真冬に咲く26の櫻の木 |
ユーザー | yudedako |
提出日時 | 2022-01-27 21:08:08 |
言語 | Scala(Beta) (3.4.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,924 bytes |
コンパイル時間 | 14,813 ms |
コンパイル使用メモリ | 278,552 KB |
実行使用メモリ | 99,624 KB |
最終ジャッジ日時 | 2024-04-26 00:09:44 |
合計ジャッジ時間 | 80,472 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,024 ms
66,084 KB |
testcase_01 | AC | 1,072 ms
65,772 KB |
testcase_02 | AC | 1,201 ms
66,572 KB |
testcase_03 | AC | 1,177 ms
66,248 KB |
testcase_04 | AC | 1,144 ms
66,304 KB |
testcase_05 | AC | 1,133 ms
66,028 KB |
testcase_06 | AC | 1,234 ms
66,628 KB |
testcase_07 | AC | 1,168 ms
66,220 KB |
testcase_08 | AC | 1,109 ms
66,252 KB |
testcase_09 | AC | 1,157 ms
66,488 KB |
testcase_10 | AC | 1,176 ms
66,156 KB |
testcase_11 | AC | 1,178 ms
66,020 KB |
testcase_12 | AC | 1,149 ms
66,044 KB |
testcase_13 | AC | 1,126 ms
65,956 KB |
testcase_14 | AC | 1,668 ms
71,616 KB |
testcase_15 | TLE | - |
testcase_16 | AC | 1,848 ms
92,752 KB |
testcase_17 | AC | 1,820 ms
69,744 KB |
testcase_18 | AC | 1,742 ms
81,520 KB |
testcase_19 | AC | 1,785 ms
69,516 KB |
testcase_20 | AC | 1,873 ms
86,548 KB |
testcase_21 | AC | 1,917 ms
99,580 KB |
testcase_22 | AC | 1,914 ms
99,624 KB |
testcase_23 | AC | 1,991 ms
71,988 KB |
testcase_24 | TLE | - |
testcase_25 | AC | 1,766 ms
72,088 KB |
testcase_26 | AC | 1,784 ms
71,936 KB |
testcase_27 | AC | 1,769 ms
81,764 KB |
testcase_28 | AC | 1,748 ms
69,652 KB |
testcase_29 | AC | 1,751 ms
67,912 KB |
testcase_30 | TLE | - |
testcase_31 | AC | 1,492 ms
67,412 KB |
testcase_32 | AC | 1,626 ms
69,820 KB |
testcase_33 | AC | 1,747 ms
79,480 KB |
testcase_34 | AC | 921 ms
65,468 KB |
testcase_35 | AC | 1,094 ms
65,896 KB |
testcase_36 | AC | 891 ms
65,184 KB |
testcase_37 | AC | 1,068 ms
66,004 KB |
testcase_38 | AC | 1,183 ms
66,140 KB |
testcase_39 | AC | 1,224 ms
66,108 KB |
testcase_40 | AC | 1,212 ms
66,156 KB |
testcase_41 | AC | 1,270 ms
66,308 KB |
ソースコード
import scala.io.StdIn.readLine import scala.reflect.ClassTag import scala.math.* type Matrix = Array[Array[Option[Long]]] extension (left: Matrix) inline def *(right: Matrix): Matrix = val row = left.length val column = right(0).length val mid = right.length Array.tabulate(row){i => Array.tabulate(column){j => (0 until mid).foldLeft(None: Option[Long]){(acc, k) => (acc, left(i)(k).flatMap(l => right(k)(j).map(r => l + r))) match case (Some(a), Some(b)) => Some(max(a, b)) case (None, r) => r case (l, None) => l } } } inline def pow(exp: Int): Matrix = val size = left.length var result = Array.tabulate(size){i => Array.tabulate(size){j => if i == j then Some(0L) else None}} var base = left var e = exp while e > 0 do if (e & 1) == 1 then result *= base base *= base e >>= 1 result @main def main = val initialColor = readLine().split(' ').map(_.toInt - 1) val maxCount = readLine().split(' ').map(_.toInt) val n = readLine().toInt val skill = Array.fill(n){ val Array(s, a, b, e) = readLine().split(' ') (s, a.toInt - 1, b.toInt - 1, e.toLong) } val graph = Array.fill(26){Array.tabulate(16){i => Array.tabulate(16){j => if i == j then Some(0L) else None}}} for (s, a, b, e) <- skill do for i <- s.map(_ - 'A') do graph(i)(a)(b) = Some(max(graph(i)(a)(b).getOrElse(e), e)) graph(i)(b)(a) = Some(max(graph(i)(b)(a).getOrElse(e), e)) for i <- 0 until 26 do graph(i) = graph(i).pow(maxCount(i)) var result = Long.MinValue for dest <- 0 until 16 do (0 until 26).foldLeft(Some(0L): Option[Long]){(acc, i) => acc.flatMap{a => graph(i)(initialColor(i))(dest).map(a + _)}} match case Some(sum) => result = max(result, sum) case None => println(if result == Long.MinValue then "Impossible" else result)