Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- private infix fun Boolean.arrow(other: Boolean) = !(this && !other)
- private val invalid = 0 to 1e9.toInt() // max / min
- private fun dfs(
- tab: List<List<Int>>,
- n: Int = tab.size - 1,
- m: Int = 0,
- dp: List<MutableList<Pair<Int, Int>>> = List(tab.size) { MutableList(tab.first().size) { invalid } }.also {
- it[0][tab.size - 1] = tab[0][tab.size - 1] to tab[0][tab.size - 1]
- }
- ): Pair<Int, Int> {
- if (n < 0 || m >= tab.size)
- return invalid
- if (dp[n][m] != invalid)
- return dp[n][m]
- dp[n][m] = run {
- val f = dfs(tab, n - 1, m, dp)
- val s = dfs(tab, n, m + 1, dp)
- val t = dfs(tab, n - 1, m + 1, dp)
- val c = tab[n][m]
- arrayOf(f.first + c, s.first + c, t.first + c * 2).maxOrNull()!! to
- arrayOf(f.second + c, s.second + c, t.second + c * 2).minOrNull()!!
- }
- return dp[n][m]
- }
- fun main() = dfs((0..11).map { readLine()!!.trim().split("\t").map(String::toInt)})
- .let { (f, s) -> println("MAX: $f; MIN: $s") }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement