結果

問題 No.165 四角で囲え！
コンテスト
ユーザー バカらっく
提出日時 2019-11-28 09:36:19
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 4,679 bytes
コンパイル時間 213 ms
コンパイル使用メモリ 13,056 KB
実行使用メモリ 47,360 KB
最終ジャッジ日時 2024-11-17 11:00:36
合計ジャッジ時間 95,530 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 6 TLE * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

# -*- coding: utf-8 -*-

class Point:
    def __init__(self, init: str):
        tmp = [int(i) for i in init.rstrip().split(" ")]
        self.x = tmp[0]
        self.y = tmp[1]
        self.point = tmp[2]

class AreaState:
    def __init__(self, count, point):
        self.count = count
        self.point = point

class Proc:
    def __init__(self):
        init = [int(i) for i in input().rstrip().split(" ")]
        self.pointCount = init[0]
        self.maxTotal = init[1]
        self.pointList = [Point(input().rstrip()) for i in range(0, self.pointCount)]
        self.xdic = self.create_x_dict()
        self.ydic = self.create_y_dict()
        self.xList = sorted(self.xdic.keys())
        self.yList = sorted(self.ydic.keys())
        self.area = self.create_area_dic()

    def create_area_dic(self):
        area = {}
        area[self.xList[0]] = {}
        area[self.xList[0]][self.yList[0]] = AreaState(0,0)

        if self.yList[0] in self.xdic[self.xList[0]]:
            area[self.xList[0]][self.yList[0]] = AreaState(1, self.xdic[self.xList[0]][self.yList[0]].point)
        for i in range(1, len(self.xList)):
            x = self.xList[i]
            y = self.yList[0]
            ast = AreaState(area[self.xList[i-1]][y].count, area[self.xList[i-1]][y].point)
            if y in self.xdic[x]:
                ast = AreaState(ast.count + 1, ast.point + self.xdic[x][y].point)
            area[x] = {}
            area[x][y] = ast

        for i in range(1, len(self.yList)):
            x = self.xList[0]
            y = self.yList[i]
            ast = AreaState(area[x][self.yList[i-1]].count, area[x][self.yList[i-1]].point)
            if x in self.ydic[y]:
                ast = AreaState(ast.count + 1, ast.point + self.ydic[y][x].point)
            area[x][y] = ast

        for xIdx in range(1, len(self.xList)):
            for yIdx in range(1, len(self.yList)):
                count = area[self.xList[xIdx - 1]][self.yList[yIdx]].count
                count += area[self.xList[xIdx]][self.yList[yIdx - 1]].count
                count -= area[self.xList[xIdx - 1]][self.yList[yIdx - 1]].count

                point = area[self.xList[xIdx - 1]][self.yList[yIdx]].point
                point += area[self.xList[xIdx]][self.yList[yIdx - 1]].point
                point -= area[self.xList[xIdx - 1]][self.yList[yIdx - 1]].point

                ast = AreaState(count, point)
                if self.yList[yIdx] in self.xdic[self.xList[xIdx]]:
                    ast = AreaState(ast.count + 1, ast.point + self.xdic[self.xList[xIdx]][self.yList[yIdx]].point)
                area[self.xList[xIdx]][self.yList[yIdx]] = ast
        return area




    def create_x_dict(self):
        ret = {}
        for p in self.pointList:
            if p.x not in ret:
                ret[p.x] = {}
            ret[p.x][p.y] = p
        return ret

    def create_y_dict(self):
        ret = {}
        for p in self.pointList:
            if p.y not in ret:
                ret[p.y] = {}
            ret[p.y][p.x] = p
        return ret
    def Proc(self):
        ans = 0
        for xidx1 in range(0, len(self.xList)):
            for xidx2 in range(xidx1, len(self.xList)):
                yIdx2 = 0
                for yIdx1 in range(0, len(self.yList)):
                    while yIdx2 < len(self.yList):
                        yIdx2 = max(yIdx2, yIdx1)
                        area = self.getAreaState(xidx1, yIdx1, xidx2, yIdx2)
                        if area.point > self.maxTotal:
                            break
                        ans = max(ans, area.count)
                        yIdx2 += 1
                        if yIdx2 >= len(self.yList):
                            break
                    if(yIdx2 >= len(self.yList)):
                        break
        return ans

    def getAreaState(self, xIdx1, yIdx1, xIdx2, yIdx2):
        baseCount = self.area[self.xList[xIdx2]][self.yList[yIdx2]].count
        basePoint = self.area[self.xList[xIdx2]][self.yList[yIdx2]].point
        if yIdx1 > 0:
            baseCount -= self.area[self.xList[xIdx2]][self.yList[yIdx1 - 1]].count
            basePoint -= self.area[self.xList[xIdx2]][self.yList[yIdx1 - 1]].point
        if xIdx1 > 0:
            baseCount -= self.area[self.xList[xIdx1-1]][self.yList[yIdx2]].count
            basePoint -= self.area[self.xList[xIdx1 - 1]][self.yList[yIdx2]].point
        if xIdx1 > 0 and yIdx1 > 0:
            baseCount += self.area[self.xList[xIdx1-1]][self.yList[yIdx1-1]].count
            basePoint += self.area[self.xList[xIdx1-1]][self.yList[yIdx1-1]].point
        return AreaState(baseCount, basePoint)

proc = Proc()
print(proc.Proc())
0