結果

問題 No.165 四角で囲え！
コンテスト
ユーザー バカらっく
提出日時 2019-11-27 04:06:13
言語 Kotlin
(2.1.0)
結果
TLE  
実行時間 -
コード長 5,640 bytes
コンパイル時間 21,907 ms
コンパイル使用メモリ 474,888 KB
実行使用メモリ 174,308 KB
最終ジャッジ日時 2024-11-07 06:51:38
合計ジャッジ時間 34,235 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other TLE * 1 -- * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.kt:4:10: warning: parameter 'arr' is never used
fun main(arr:Array<String>) {
         ^

ソースコード

diff # 

import java.util.*
import kotlin.contracts.contract

fun main(arr:Array<String>) {
    val proc = MainProc(readLine()!!.split(" ").map { it.toInt() })
    proc.Proc()
}

class MainProc(inpt:List<Int>) {
    private val pointCount = inpt[0]
    val maxTotal = inpt[1]
    private val pointList = (1..pointCount).map { Point(readLine()!!.split(" ").map { it.toLong() }) }
    private val xDic = getXDic()
    private val yDic = getYDic()
    private val xList = xDic.keys.sorted()
    private val yList = yDic.keys.sorted();
    private val area = mutableMapOf<Long, MutableMap<Long, AreaState>>()

    public fun Proc() {
        area[xList.first()] = mutableMapOf()
        if(xDic[xList.first()]!!.containsKey(yList.first())) {
            val p = xDic[xList.first()]!![yList.first()]!!
            area[xList.first()]!![yList.first()] = AreaState(1, p.point)
         } else {
            area[xList.first()]!![yList.first()] = AreaState(0,0)
        }
        for(i in (1 until xList.size)) {
            val x = xList[i]
            val y = yList.first()

            val p = xDic[x]!![y]
            val prev = area[xList[i-1]]!![y]!!
            var current = AreaState(prev.pointCount, prev.pointTotal)
            p?.let { current = AreaState(prev.pointCount + 1, prev.pointTotal + it.point) }
            area[x] = mutableMapOf()
            area[x]!![y] = current
        }

        for(i in (1 until yList.size)) {
            val x = xList.first()
            val y = yList[i]
            val p = xDic[x]!![y]
            val prev = area[x]!![yList[i-1]]!!
            var current = AreaState(prev.pointCount, prev.pointTotal)
            p?.let { current = AreaState(prev.pointCount + 1, prev.pointTotal + it.point) }
            area[x]!![y] = current
        }

        for(xindex in (1 until xList.size)) {
            for(yindex in (1 until yList.size)) {
                val x = xList[xindex]
                val y = yList[yindex]
                val p = xDic[x]!![y]
                val prev1 = area[x]!![yList[yindex-1]]!!
                val prev2 = area[xList[xindex-1]]!![y]!!
                val prev3 = area[xList[xindex-1]]!![yList[yindex-1]]!!
                var current = AreaState(prev1.pointCount + prev2.pointCount - prev3.pointCount, prev1.pointTotal + prev2.pointTotal - prev3.pointTotal)
                p?.let { current = AreaState(current.pointCount + 1, current.pointTotal + it.point) }
                area[x]!![y] = current
            }
        }

        val dic = mutableMapOf<Int, MutableMap<Int, MutableMap<Int, MutableMap<Int, Boolean>>>>()
        var ans = 0
        val queue = Stack<List<Int>>()
        queue.push(listOf(0,0,0,0))
        while (queue.isNotEmpty()) {
            var task = queue.pop()
            var xidx = task[0]
            var yidx = task[1]
            var xidx2 = task[2]
            var yidx2 = task[3]
            if(xidx2 > xList.lastIndex) {
                continue
            }
            if(yidx2 > yList.lastIndex) {
                continue
            }
            if(!dic.containsKey(xidx)) {
                dic[xidx] = mutableMapOf()
            }
            if(!dic[xidx]!!.containsKey(yidx)) {
                dic[xidx]!![yidx] = mutableMapOf()
            }
            if(!dic[xidx]!![yidx]!!.containsKey(xidx2)) {
                dic[xidx]!![yidx]!![xidx2] = mutableMapOf()
            }
            if(dic[xidx]!![yidx]!![xidx2]!!.containsKey(yidx2)) {
                continue
            }
            dic[xidx]!![yidx]!![xidx2]!![yidx] = true
            val area = getAreaState(xidx, yidx, xidx2, yidx2)
            if(area.pointTotal > maxTotal) {
                queue.push(listOf(xidx + 1, yidx, Math.max(xidx + 1, xidx2), yidx2))
                queue.push(listOf(xidx, yidx + 1, xidx2, Math.max(yidx+1 ,yidx)))
                continue
            }
            ans = Math.max(ans, area.pointCount)
            queue.push(listOf(xidx, yidx, xidx2 + 1, yidx2))
            queue.push(listOf(xidx, yidx, xidx2, yidx2 + 1))
        }
        println(ans)
    }

    private fun getAreaState(xidx:Int, yidx:Int, xidx2:Int, yidx2:Int):AreaState {
        val x2 = xList[xidx2]
        val y2 = yList[yidx2]
        var point = area[x2]!![y2]!!.pointTotal
        var count = area[x2] !![y2]!!.pointCount
        if(xidx > 0) {
            point -= area[xList[xidx - 1]]!![y2]!!.pointTotal
            count -= area[xList[xidx - 1]]!![y2]!!.pointCount
        }
        if(yidx > 0) {
            point -= area[x2]!![yList[yidx-1]]!!.pointTotal
            count -= area[x2]!![yList[yidx-1]]!!.pointCount
        }
        if(xidx > 0 && yidx > 0) {
            point += area[xList[xidx-1]]!![yList[yidx-1]]!!.pointTotal
            count += area[xList[xidx-1]]!![yList[yidx-1]]!!.pointCount
        }
        return AreaState(count, point)
    }
    private fun getXDic():Map<Long, Map<Long, Point>> {
        val ret = mutableMapOf<Long, MutableMap<Long, Point>>()
        for(p in pointList) {
            if(!ret.containsKey(p.x)) {
                ret[p.x] = mutableMapOf()
            }
            ret[p.x]!![p.y] = p
        }
        return ret
    }
    private fun getYDic():Map<Long, Map<Long, Point>> {
        val ret = mutableMapOf<Long, MutableMap<Long, Point>>()
        for(p in pointList) {
            if(!ret.containsKey(p.y)) {
                ret[p.y] = mutableMapOf()
            }
            ret[p.y]!![p.x] = p
        }
        return ret
    }
}

class Point(inpt:List<Long>) {
    val x = inpt[0]
    val y = inpt[1]
    val point = inpt[2].toInt()
}

class AreaState(val pointCount:Int, val pointTotal:Int)
0