Advertisement
paranid5

11 10.11

Nov 10th, 2021
953
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Kotlin 1.07 KB | None | 0 0
  1. private infix fun Boolean.arrow(other: Boolean) = !(this && !other)
  2.  
  3. private val invalid = 0 to 1e9.toInt() // max / min
  4.  
  5. private fun dfs(
  6.     tab: List<List<Int>>,
  7.     n: Int = tab.size - 1,
  8.     m: Int = tab.size - 1,
  9.     dp: List<MutableList<Pair<Int, Int>>> = List(tab.size) { MutableList(tab.first().size) { invalid } }.also {
  10.         it[0][0] = tab[0][0] to tab[0][0]
  11.     }
  12. ): Pair<Int, Int> {
  13.     if (n < 0 || m < 0)
  14.         return invalid
  15.  
  16.     if (dp[n][m] != invalid)
  17.         return dp[n][m]
  18.  
  19.     dp[n][m] = when {
  20.         n in 5..11 && m == 13 -> dfs(tab, n - 1, m, dp)
  21.         n == 5 && m in 6..12 -> dfs(tab, n, m - 1, dp)
  22.  
  23.         else -> {
  24.             val f = dfs(tab, n - 1, m, dp)
  25.             val s = dfs(tab, n, m - 1, dp)
  26.             arrayOf(f.first, s.first).maxOrNull()!! to arrayOf(f.second, s.second).minOrNull()!!
  27.         }
  28.     }.let { (f, s) -> tab[n][m].let { f + it to s + it } }
  29.  
  30.     return dp[n][m]
  31. }
  32.  
  33. fun main() = dfs((0..15).map { readLine()!!.trim().split("\t").map(String::toInt)})
  34.     .let { (f, s) -> println("MAX: $f; MIN: $s") }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement