結果
| 問題 | No.165 四角で囲え！ |
| ユーザー |
 バカらっく
|
| 提出日時 | 2019-11-27 04:06:13 |
| 言語 | Kotlin (1.9.23) |
| 結果 |
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 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
コンパイルメッセージ
Main.kt:4:10: warning: parameter 'arr' is never used
fun main(arr:Array<String>) {
^
ソースコード
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)