Submission #9335697

---

Source Code Expand

fun main(args: Array<String>) {
    val N = readLine()!!.toInt()
    val a = readLine()!!.split(" ").map{it.toLong()}
    val b = Array(N + 1) { 0L }
    for (i in a.indices) {
        b[i + 1] = a[i] + b[i]
    }

    var l = (-1e15).toLong()
    var u = 1e15.toLong()

    fun judge(c: Long): Boolean {
        val dp1 = Array(N + 1) { 0 }
        val dp2 = Array(N + 1) { 0 }

        for (i in N-1 downTo 0) {
            dp1[i] = -2 * N
            dp2[i] = 2 * N
            for (j in i + 1 .. N) {
                val t = if (b[j] - b[i] >= c) 1 else -1
                dp1[i] = Math.max(dp1[i], dp2[j] + t)
                dp2[i] = Math.min(dp2[i], dp1[j] + t)
            }
        }

        return dp1[0] >= 0
    }

    while (u - l > 1) {
        val c = (l + u) / 2

        if (judge(c)) {
            l = c
        } else {
            u = c
        }
    }

    println(l)
}

Submission Info

Judge Result