結果
| 問題 | No.957 植林 |
| ユーザー |
 da_louis
|
| 提出日時 | 2021-02-28 23:08:01 |
| 言語 | Kotlin (1.9.23) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 22,984 bytes |
| コンパイル時間 | 28,407 ms |
| コンパイル使用メモリ | 490,440 KB |
| 実行使用メモリ | 117,044 KB |
| 最終ジャッジ日時 | 2024-04-12 10:58:51 |
| 合計ジャッジ時間 | 47,909 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 324 ms
66,124 KB |
| testcase_01 | AC | 332 ms
100,816 KB |
| testcase_02 | AC | 337 ms
69,608 KB |
| testcase_03 | AC | 1,451 ms
108,816 KB |
| testcase_04 | AC | 1,085 ms
89,748 KB |
| testcase_05 | AC | 1,303 ms
110,976 KB |
| testcase_06 | AC | 1,088 ms
110,876 KB |
| testcase_07 | AC | 1,783 ms
87,580 KB |
| testcase_08 | AC | 792 ms
111,000 KB |
| testcase_09 | AC | 691 ms
110,968 KB |
| testcase_10 | AC | 879 ms
111,152 KB |
| testcase_11 | AC | 853 ms
109,116 KB |
| testcase_12 | AC | 814 ms
108,800 KB |
| testcase_13 | AC | 635 ms
87,972 KB |
| testcase_14 | AC | 795 ms
110,872 KB |
| testcase_15 | AC | 795 ms
108,948 KB |
| testcase_16 | AC | 694 ms
89,852 KB |
| testcase_17 | AC | 720 ms
87,832 KB |
| testcase_18 | TLE | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
コンパイルメッセージ
Main.kt:255:13: warning: 'appendln(Int): kotlin.text.StringBuilder /* = java.lang.StringBuilder */' is deprecated. Use appendLine instead. Note that the new method always appends the line feed character '\n' regardless of the system line separator.
appendln(n)
^
Main.kt:288:48: warning: 'toByte(): Byte' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead.
private fun Byte.isNumeric() = this in '0'.toByte()..'9'.toByte()
^
Main.kt:288:62: warning: 'toByte(): Byte' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead.
private fun Byte.isNumeric() = this in '0'.toByte()..'9'.toByte()
^
Main.kt:289:68: warning: 'toByte(): Byte' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead.
private fun Byte.toNumVal() = if (this.isNumeric()) this - '0'.toByte() else error("$this is not numeric")
^
Main.kt:321:22: warning: 'toByte(): Byte' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead.
if (b == '-'.toByte()) {
^
Main.kt:347:22: warning: 'toByte(): Byte' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead.
if (b == '-'.toByte()) {
^
Main.kt:353:22: warning: 'toByte(): Byte' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead.
if (b == '.'.toByte()) {
^
ソースコード
import java.io.ByteArrayInputStream
import java.io.ByteArrayOutputStream
import java.io.PrintStream
import java.math.BigInteger
fun main() = if (localEnv && execChecker) checker() else p957()
fun p957() = solve()
@OptIn(ExperimentalStdlibApi::class)
private fun solve() = Messiah_p957(MOD).exec {
val (h, w) = readInt(2)
val costs = readLong(h, w)
val bonusRow = readLong(h)
val bonusCol = readLong(w)
// [0, h * w) : grid
// [h * w, h * w + h) : row
// [h * w + h, h * w + h + w): col
val s = h * w + h + w
val t = s + 1
val mf = MaxFlow(t + 1)
fun gridId(y: Int, x: Int) = y * w + x
fun rowId(y: Int) = h * w + y
fun colId(x: Int) = h * w + h + x
val inf = Long.MAX_VALUE / 3
for (y in h.indices) for (x in w.indices) {
val id = gridId(y, x)
mf.addEdge(s, id, costs[y][x])
mf.addEdge(id, rowId(y), inf)
mf.addEdge(id, colId(x), inf)
}
for (y in h.indices) mf.addEdge(rowId(y), t, bonusRow[y])
for (x in w.indices) mf.addEdge(colId(x), t, bonusCol[x])
debugExec {
for (edge in mf.edges) {
debugln("${edge.from} ${edge.to} ${edge.cap}")
}
}
val maxFlow = mf.maxFlow(s, t)
val bonusSum = bonusRow.sum() + bonusCol.sum()
val answer = bonusSum - maxFlow
println(answer)
}
/**
* convert from [AtCoderLibraryForJava - MaxFlow](https://github.com/NASU41/AtCoderLibraryForJava/blob/3d5e128641057adbce8b4a727bba4079b8fa2c02/MinCostFlow/MinCostFlow.java)
*/
private class MaxFlow(private val n: Int) {
inner class CapEdge internal constructor(val from: Int, val to: Int, var cap: Long, val rev: Int)
private var m = 0
val edges: ArrayList<CapEdge> = ArrayList()
private val count: IntArray = IntArray(n)
private val g: Array<Array<CapEdge?>> = Array(n) { emptyArray<CapEdge?>() }
fun addEdge(from: Int, to: Int, cap: Long): Int {
rangeCheck(from, 0, n)
rangeCheck(to, 0, n)
nonNegativeCheck(cap, "Capacity")
val e = CapEdge(from, to, cap, count[to])
count[from]++
count[to]++
edges.add(e)
return m++
}
fun getEdge(i: Int): CapEdge {
rangeCheck(i, 0, m)
return edges[i]
}
fun changeEdge(i: Int, newCap: Long, newFlow: Long) {
rangeCheck(i, 0, m)
nonNegativeCheck(newCap, "Capacity")
require(newFlow <= newCap) { String.format("Flow %d is greater than capacity %d.", newCap, newFlow) }
val e = edges[i]
val er = g[e.to][e.rev]
e.cap = newCap - newFlow
er!!.cap = newFlow
}
private fun buildGraph() {
for (i in 0 until n) {
g[i] = arrayOfNulls(count[i])
}
val idx = IntArray(n)
for (e in edges) {
g[e.to][idx[e.to]++] = CapEdge(e.to, e.from, 0, idx[e.from])
g[e.from][idx[e.from]++] = e
}
}
fun maxFlow(s: Int, t: Int): Long {
return flow(s, t, INF)
}
fun flow(s: Int, t: Int, flowLimit: Long): Long {
rangeCheck(s, 0, n)
rangeCheck(t, 0, n)
buildGraph()
var flow: Long = 0
val level = IntArray(n)
val que = IntArray(n)
val iter = IntArray(n)
while (true) {
java.util.Arrays.fill(level, -1)
dinicBFS(s, t, level, que)
if (level[t] < 0) return flow
java.util.Arrays.fill(iter, 0)
while (true) {
val d = dinicDFS(t, s, flowLimit - flow, iter, level)
if (d <= 0) break
flow += d
}
}
}
private fun dinicBFS(s: Int, t: Int, level: IntArray, que: IntArray) {
var hd = 0
var tl = 0
que[tl++] = s
level[s] = 0
while (tl > hd) {
val u = que[hd++]
for (e in g[u]) {
val v = e!!.to
if (e.cap <= 0 || level[v] >= 0) continue
level[v] = level[u] + 1
if (v == t) return
que[tl++] = v
}
}
}
private fun dinicDFS(cur: Int, s: Int, f: Long, iter: IntArray, level: IntArray): Long {
if (cur == s) return f
var res: Long = 0
while (iter[cur] < count[cur]) {
val er = g[cur][iter[cur]++]
val u = er!!.to
val e = g[u][er.rev]
if (level[u] >= level[cur] || e!!.cap <= 0) continue
val d = dinicDFS(u, s, kotlin.math.min(f - res, e.cap), iter, level)
if (d <= 0) continue
e.cap -= d
er.cap += d
res += d
if (res == f) break
}
return res
}
fun fordFulkersonMaxFlow(s: Int, t: Int): Long {
return fordFulkersonFlow(s, t, INF)
}
fun fordFulkersonFlow(s: Int, t: Int, flowLimit: Long): Long {
rangeCheck(s, 0, n)
rangeCheck(t, 0, n)
buildGraph()
val used = BooleanArray(n)
var flow: Long = 0
while (true) {
java.util.Arrays.fill(used, false)
val f = fordFulkersonDFS(s, t, flowLimit - flow, used)
if (f <= 0) return flow
flow += f
}
}
private fun fordFulkersonDFS(cur: Int, t: Int, f: Long, used: BooleanArray): Long {
if (cur == t) return f
used[cur] = true
for (e in g[cur]) {
if (used[e!!.to] || e.cap <= 0) continue
val d = fordFulkersonDFS(e.to, t, kotlin.math.min(f, e.cap), used)
if (d <= 0) continue
e.cap -= d
g[e.to][e.rev]!!.cap += d
return d
}
return 0
}
fun minCut(s: Int): BooleanArray {
rangeCheck(s, 0, n)
val reachable = BooleanArray(n)
val stack = IntArray(n)
var ptr = 0
stack[ptr++] = s
reachable[s] = true
while (ptr > 0) {
val u = stack[--ptr]
for (e in g[u]) {
val v = e!!.to
if (reachable[v] || e.cap <= 0) continue
reachable[v] = true
stack[ptr++] = v
}
}
return reachable
}
private fun rangeCheck(i: Int, minInclusive: Int, maxExclusive: Int) {
if (i < minInclusive || i >= maxExclusive) {
throw IndexOutOfBoundsException(String.format("Index %d out of bounds for length %d", i, maxExclusive))
}
}
private fun nonNegativeCheck(cap: Long, attribute: String) {
require(cap >= 0) { String.format("%s %d is negative.", attribute, cap) }
}
companion object {
private const val INF = Long.MAX_VALUE
}
}
private const val MOD = 1_000_000_007
// region kokokara template dayo (^o^)
private const val execChecker = false
private val localEnv =
runCatching { "ENABLE_DEBUG_MODE_FOR_COMPETITIVE_PROGRAMING" in System.getenv() }.getOrNull() ?: false
private fun checker() = Messiah_p957(MOD).exec {
debugln("#######################################################")
debugln("############### executing check mode. ###############")
debugln("#######################################################")
fun getOutPut(input: String, action: () -> Unit): String {
System.setIn(ByteArrayInputStream(input.toByteArray()))
val sysOut = ByteArrayOutputStream()
System.setOut(PrintStream(sysOut))
action()
return sysOut.toString()
}
val wrongCases = mutableSetOf<List<String>>()
while (wrongCases.size < 10) {
/*
examples
val randomString = (1..20).map { ('a'..'z').random() }.joinToString("")
val randomNum = Random.nextInt(0,2000)
*/
val n = 0
val input = buildString {
appendln(n)
}
val solve = getOutPut(input, ::solve)
val greedy = getOutPut(input, ::greedy)
if (solve != greedy && wrongCases.add(listOf(solve, greedy))) {
debugln("#################### wrong case: ${wrongCases.size} ####################")
debugln("input:")
debugln(input)
debugln("solve:")
debugln(solve)
debugln("greedy:")
debugln(greedy)
}
}
}
private fun greedy() = Messiah_p957(MOD).exec {
TODO()
}
@Suppress("ClassName", "unused", "FunctionName", "PropertyName")
private class Messiah_p957(private val mod: Int) {
//////////////////////////////////////////////////
// IO
//////////////////////////////////////////////////
private val input = System.`in`
private val buffer = ByteArray(1024)
private var pointer = 0
private var bufferLength = 0
private val sb = StringBuilder()
private fun Byte.isPrintable() = this in 33..126
private fun Byte.isNumeric() = this in '0'.toByte()..'9'.toByte()
private fun Byte.toNumVal() = if (this.isNumeric()) this - '0'.toByte() else error("$this is not numeric")
private val lineSeparator: String = System.lineSeparator()
private fun hasNextByte(): Boolean {
return if (pointer < bufferLength) true else {
pointer = 0
bufferLength = input.read(buffer)
bufferLength > 0
}
}
private fun readByte(): Byte = if (hasNextByte()) buffer[pointer++] else -1
private fun skipUnprintable() = run { while (hasNextByte() && !buffer[pointer].isPrintable()) pointer++ }
private fun hasNext(): Boolean = run { skipUnprintable() }.run { hasNextByte() }
private fun hasNextOrError() = if (!hasNext()) error("has no next element.") else Unit
fun readString(): String {
hasNextOrError()
val sb = StringBuilder()
var b = readByte()
while (b.isPrintable()) {
sb.appendCodePoint(b.toInt())
b = readByte()
}
return sb.toString()
}
fun readLong(): Long {
hasNextOrError()
var n = 0L
var negative = false
var b = readByte()
if (b == '-'.toByte()) {
negative = true
b = readByte()
}
if (!b.isNumeric()) error("$b is not numeric.")
while (true) {
when {
b.isNumeric() -> n = n * 10 + b.toNumVal()
b.toInt() == -1 || !b.isPrintable() -> return if (negative) -n else n
else -> error("failed to parse. [n=$n, b=$b]")
}
b = readByte()
}
}
fun readInt() = readLong()
.let { if (it in Int.MIN_VALUE..Int.MAX_VALUE) it.toInt() else error("$it is not in range of Int.") }
fun readIntAsIndex() = readInt().dec()
fun readDouble(): Double {
hasNextOrError()
var n = 0.0
var div = 1.0
var negative = false
var b = readByte()
if (b == '-'.toByte()) {
negative = true
b = readByte()
}
do n = n * 10 + b.toNumVal()
while (run { b = readByte() }.run { b.isNumeric() })
if (b == '.'.toByte()) {
while (run { b = readByte() }.run { b.isNumeric() })
n += b.toNumVal() / (run { div *= 10 }.run { div })
}
return if (negative) -n else n
}
fun readString(size: Int): Array<String> = Array(size) { readString() }
@Suppress("UNUSED_PARAMETER")
fun readChars(h: Int, w: Int): Array<CharArray> = Array(h) { readString().toCharArray() }
fun readLong(size: Int): LongArray = LongArray(size) { readLong() }
fun readLong(h: Int, w: Int): Array<LongArray> = Array(h) { readLong(w) }
fun readInt(size: Int): IntArray = IntArray(size) { readInt() }
fun readInt(h: Int, w: Int): Array<IntArray> = Array(h) { readInt(w) }
fun readIntAsIndex(size: Int): IntArray = IntArray(size) { readIntAsIndex() }
fun readIntAsIndex(h: Int, w: Int): Array<IntArray> = Array(h) { readIntAsIndex(w) }
fun readDouble(size: Int): DoubleArray = DoubleArray(size) { readDouble() }
fun readDouble(h: Int, w: Int): Array<DoubleArray> = Array(h) { readDouble(w) }
fun readBooleanWithSeparator(size: Int, trueElement: String): BooleanArray =
BooleanArray(size) { readString() == trueElement }
fun readBooleanWithSeparator(h: Int, w: Int, trueElement: String): Array<BooleanArray> =
Array(h) { readBooleanWithSeparator(w, trueElement) }
@Suppress("UNUSED_PARAMETER")
fun readBooleanWithoutSeparator(size: Int, trueElement: Char): BooleanArray =
readString().map { it == trueElement }.toBooleanArray()
fun readBooleanWithoutSeparator(h: Int, w: Int, trueElement: Char): Array<BooleanArray> =
Array(h) { readBooleanWithoutSeparator(w, trueElement) }
fun println(): Unit = run { sb.append(lineSeparator) }
fun print(any: Any): Unit = run { sb.append(any.toString()) }
fun println(any: Any): Unit = run { sb.append(any.toString() + lineSeparator) }
fun flush() = run { kotlin.io.println(sb); sb.clear() }
fun debug(any: Any): Unit = run { if (localEnv) System.err.print(any) }
fun debugln(any: Any): Unit = run { if (localEnv) System.err.println(any) }
fun debugln(): Unit = run { if (localEnv) System.err.println() }
fun debugExec(action: () -> Unit): Unit = run { if (localEnv) action() }
fun exec(action: Messiah_p957.() -> Unit) {
var t: Throwable? = null
Thread(null, { action() }, "solve", 128 * 1024 * 1024)
.apply { setUncaughtExceptionHandler { _, t1 -> t = t1 } }
.apply { start() }.join()
t?.let { throw it }
kotlin.io.print(sb)
}
fun readLine(): Nothing = error("readLine is disabled.")
//////////////////////////////////////////////////
// MOD
//////////////////////////////////////////////////
private val modIsPrime: Boolean = MOD.toBigInteger().isProbablePrime(100)
fun Long.invertMod(): Long = if (modIsPrime) this.powMod(MOD - 2L) else invGcd(this).second
fun Long.safeMod(): Long = (this % MOD).let { if (it < 0) it + MOD else it }
fun Long.plusMod(other: Long): Long = this.plus(other).safeMod()
fun Long.minusMod(other: Long): Long = this.minus(other).safeMod()
fun Long.timesMod(other: Long): Long = this.times(other).safeMod()
fun Long.divMod(other: Long): Long = this.times(other.invertMod()).safeMod()
fun Long.powMod(p: Long): Long {
var x = this % MOD
var y = p
var result = 1L
while (y > 0) {
if (y % 2 == 1L) result = (result * x) % MOD
y = y shr 1
x = (x * x) % MOD
}
return result
}
fun Long.powMod(p: Long, m: Int): Long {
var x = this % m
var y = p
var result = 1L
while (y > 0) {
if (y % 2 == 1L) result = (result * x) % m
y = y shr 1
x = (x * x) % m
}
return result
}
fun invGcd(a: Long): Pair<Long, Long> {
val am = a.safeMod()
if (a == 0L) return MOD.toLong() to 0L
var s = MOD.toLong()
var t = am
var m0 = 0L
var m1 = 1L
while (t != 0L) {
val u = s / t
s -= t * u
m0 -= m1 * u
var temp = s
s = t
t = temp
temp = m0
m0 = m1
m1 = temp
}
if (m0 < 0) m0 += MOD / s
return s to m0
}
//////////////////////////////////////////////////
// Misc
//////////////////////////////////////////////////
/**
* `n.indices()` is sugar syntax of `0 until n`.
*/
val Int.indices: IntRange get() = 0 until this
/**
* `[index] in [this]` is sugar syntax of `index in 0 until [this]`.
*/
operator fun Int.contains(index: Int): Boolean = index in this.indices
/**
* `[this].mapIndices { transform }` is sugar syntax of `(0 until [this]).map{ transform(it) }`.
*/
inline fun <R> Int.mapIndices(transform: (Int) -> R): List<R> = this.indices.map(transform)
/**
* `[this].mapIndices(x) { transform }` is sugar syntax of
* `(0 until [this]).map{ y1-> (0 until [x]).map { x1-> transform(y1,x1) } }`.
*/
inline fun <R> Int.mapIndices(x: Int, transform: (Int, Int) -> R): List<List<R>> =
this.mapIndices { y1 -> x.mapIndices { x1 -> transform(y1, x1) } }
/**
* `[this].mapIndices(x) { transform }` is sugar syntax of
* `(0 until [this]).map{ y1-> (0 until [x]).map { x1-> transform(y1,x1) } }`.
*/
inline fun <R> Int.flatMapIndices(x: Int, transform: (Int, Int) -> R): List<R> =
this.indices.flatMap { y1 -> x.mapIndices { x1 -> transform(y1, x1) } }
/**
* `[this].forEachIndices { transform }` is sugar syntax of `(0 until [this]).map{ transform(it) }`.
*/
inline fun Int.forEachIndices(transform: (Int) -> Unit): Unit = this.indices.forEach(transform)
/**
* `[this].forEachIndices(x) { transform }` is sugar syntax of
* `(0 until [this]).map{ y1-> (0 until [x]).map { x1-> transform(y1,x1) } }`.
*/
inline fun Int.forEachIndices(x: Int, transform: (Int, Int) -> Unit): Unit =
this.forEachIndices { y1 -> x.forEachIndices { x1 -> transform(y1, x1) } }
/**
* 正の方向へ丸める割り算
*/
fun Int.ceilDiv(b: Int): Int = this.also { check(b != 0) }.run {
when {
b < 0 -> (-this).ceilDiv(-b)
this > 0 -> ((this + b - 1) / b)
else -> (this / b)
}
}
/**
* 負の方向へ丸める割り算
*/
fun Int.floorDiv(b: Int): Int = -(-this).ceilDiv(b)
/**
* 正の方向へ丸める割り算
*/
fun Long.ceilDiv(b: Long): Long = this.also { check(b != 0L) }.run {
when {
b < 0 -> (-this).ceilDiv(-b)
this > 0 -> ((this + b - 1) / b)
else -> (this / b)
}
}
/**
* 負の方向へ丸める割り算
*/
fun Long.floorDiv(b: Long): Long = -(-this).ceilDiv(b)
/**
* 0から離れている方向の[b]の倍数へ切り上げる
*/
fun Long.ceilMultipleOf(b: Long): Long = this / b * b + if (this % b == 0L) 0L else b
/**
* get characters numeric value.
* e.g.: '0' to 0
*/
fun Char.toNumericValue(): Int = this - '0'
fun Char.caseToIndexedValue(): Int = this - 'a'
fun String.toPoweredLong(p: Int): Long {
check(this.isNotBlank())
if (this[0] == '-') return -this.drop(1).toPoweredLong(p)
var mulI = 1L
repeat(p) { mulI *= 10 }
val i = this.indexOf('.').takeIf { it != -1 } ?: return this.toLong() * mulI
var mulD = 1L
repeat(p - this.length + i + 1) { mulD *= 10 }
return this.slice(0 until i).toLong() * mulI + this.slice(i + 1..this.lastIndex).toLong() * mulD
}
fun String.toBigIntegerWithBase(base: BigInteger): BigInteger {
var sum = BigInteger.ZERO
var bs = BigInteger.ONE
for (c in this.reversed()) {
sum += bs * (Character.getNumericValue(c)).toBigInteger()
bs *= base
}
return sum
}
/**
* make triple. e.g.:`1 to 2 to 3`
*/
infix fun <A, B, C> Pair<A, B>.to(c: C): Triple<A, B, C> = Triple(this.first, this.second, c)
fun YesNo(b: Boolean): String = if (b) Yes else No
val Yes = "Yes"
val No = "No"
fun YES_NO(b: Boolean): String = if (b) YES else NO
val YES = "YES"
val NO = "NO"
fun IntArray.swap(a: Int, b: Int): Unit = run { val temp = this[a]; this[a] = this[b]; this[b] = temp }
fun LongArray.swap(a: Int, b: Int): Unit = run { val temp = this[a]; this[a] = this[b]; this[b] = temp }
fun CharArray.swap(a: Int, b: Int): Unit = run { val temp = this[a]; this[a] = this[b]; this[b] = temp }
fun <T> Array<T>.swap(a: Int, b: Int): Unit = run { val temp = this[a]; this[a] = this[b]; this[b] = temp }
fun <T> MutableList<T>.swap(a: Int, b: Int): Unit = run { val temp = this[a]; this[a] = this[b]; this[b] = temp }
fun IntArray.changeMinOf(i: Int, v: Int): Boolean = run { if (this[i] > v) run { this[i] = v; true } else false }
fun IntArray.changeMaxOf(i: Int, v: Int): Boolean = run { if (this[i] < v) run { this[i] = v; true } else false }
fun LongArray.changeMinOf(i: Int, v: Long): Boolean = run { if (this[i] > v) run { this[i] = v; true } else false }
fun LongArray.changeMaxOf(i: Int, v: Long): Boolean = run { if (this[i] < v) run { this[i] = v; true } else false }
fun Array<IntArray>.changeMinOf(i: Int, j: Int, v: Int): Boolean = this[i].changeMinOf(j, v)
fun Array<IntArray>.changeMaxOf(i: Int, j: Int, v: Int): Boolean = this[i].changeMaxOf(j, v)
fun Array<LongArray>.changeMinOf(i: Int, j: Int, v: Long): Boolean = this[i].changeMinOf(j, v)
fun Array<LongArray>.changeMaxOf(i: Int, j: Int, v: Long): Boolean = this[i].changeMaxOf(j, v)
fun Array<Array<IntArray>>.changeMinOf(i: Int, j: Int, k: Int, v: Int): Boolean = this[i].changeMinOf(j, k, v)
fun Array<Array<IntArray>>.changeMaxOf(i: Int, j: Int, k: Int, v: Int): Boolean = this[i].changeMaxOf(j, k, v)
fun Array<Array<LongArray>>.changeMinOf(i: Int, j: Int, k: Int, v: Long): Boolean = this[i].changeMinOf(j, k, v)
fun Array<Array<LongArray>>.changeMaxOf(i: Int, j: Int, k: Int, v: Long): Boolean = this[i].changeMaxOf(j, k, v)
/**
* same usage as `IntArray.scan`, but it will faster than that.
*/
inline fun IntArray.scanArray(initial: Int, operation: (acc: Int, Int) -> Int): IntArray {
val accumulator = IntArray(this.size + 1).apply { this[0] = initial }
for (i in this.indices) accumulator[i + 1] = operation(accumulator[i], this[i])
return accumulator
}
/**
* same usage as `LongArray.scan`, but it will faster than that.
*/
inline fun LongArray.scanArray(initial: Long, operation: (acc: Long, Long) -> Long): LongArray {
val accumulator = LongArray(this.size + 1).apply { this[0] = initial }
for (i in this.indices) accumulator[i + 1] = operation(accumulator[i], this[i])
return accumulator
}
/**
* same usage as `IntArray.scanReduce`, but it will faster than that.
*/
inline fun IntArray.scanReduceArray(operation: (acc: Int, Int) -> Int): IntArray {
val accumulator = IntArray(this.size).apply { this[0] = this@scanReduceArray[0] }
for (i in 1..this.lastIndex) accumulator[i] = operation(accumulator[i - 1], this[i])
return accumulator
}
/**
* same usage as `LongArray.scanReduce`, but it will faster than that.
*/
inline fun LongArray.scanReduceArray(operation: (acc: Long, Long) -> Long): LongArray {
val accumulator = LongArray(this.size).apply { this[0] = this@scanReduceArray[0] }
for (i in 1..this.lastIndex) accumulator[i] = operation(accumulator[i - 1], this[i])
return accumulator
}
}
// endregion kokomade template dayo (^o^)