結果

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

ソースコード

diff # 

import java.util.concurrent.CountDownLatch

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
            }
        }

        var ans = 0
        for(xidx in xList.indices) {
            for(yidx in yList.indices) {
                for(xidx2 in (xidx..xList.lastIndex)) {
                    for(yidx2 in (yidx..yList.lastIndex)) {
                        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
                        }
                        if(point > this.maxTotal) {
                            break
                        }
                        ans = Math.max(ans, count)
                    }
                }
            }
        }
        println(ans)
    }
    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