結果

問題 No.165 四角で囲え！
ユーザー バカらっくバカらっく
提出日時 2019-11-27 03:34:51
言語 Kotlin
(1.9.23)
結果
TLE  
実行時間 -
コード長 4,923 bytes
コンパイル時間 20,419 ms
コンパイル使用メモリ 467,128 KB
実行使用メモリ 130,072 KB
最終ジャッジ日時 2024-11-07 05:43:24
合計ジャッジ時間 54,439 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4,230 ms
122,556 KB
testcase_01 AC 333 ms
91,276 KB
testcase_02 AC 331 ms
55,392 KB
testcase_03 AC 329 ms
55,096 KB
testcase_04 AC 342 ms
55,304 KB
testcase_05 TLE -
testcase_06 AC 2,510 ms
107,640 KB
testcase_07 AC 334 ms
54,984 KB
testcase_08 AC 331 ms
55,076 KB
testcase_09 AC 331 ms
55,296 KB
testcase_10 AC 318 ms
51,756 KB
testcase_11 AC 2,920 ms
116,388 KB
testcase_12 AC 1,318 ms
110,172 KB
testcase_13 AC 2,230 ms
112,652 KB
testcase_14 AC 1,130 ms
75,900 KB
testcase_15 AC 1,081 ms
108,688 KB
testcase_16 TLE -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
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(xidx2 in (xidx..xList.lastIndex)) {
                var yidx2 = 0
                for(yidx in yList.indices) {
                    for(i 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)
                        yidx2++
                        if(yidx2 > yList.lastIndex) {
                            break
                        }
                    }
                    if(yidx2 > yList.lastIndex) {
                        break
                    }
                }
            }
        }
        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