結果

問題 No.165 四角で囲え！
コンテスト
ユーザー cologne
提出日時 2026-02-05 13:12:17
言語 PyPy3
(7.3.17)
結果
AC  
実行時間 2,122 ms / 5,000 ms
コード長 1,626 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,277 ms
コンパイル使用メモリ 82,300 KB
実行使用メモリ 83,356 KB
最終ジャッジ日時 2026-02-05 13:12:38
合計ジャッジ時間 19,092 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from bisect import bisect_left
from typing import List, Tuple


def int1(x: str, /): return int(x) - 1


def input(): return sys.stdin.readline().rstrip('\n')


def dbg(*args, **kwargs):
    print(*(repr(arg) for arg in args), *(f'{k}: {repr(v)}' for k, v in kwargs.items()),
          sep='; ', file=sys.stderr, flush=True)


def main():
    n, b = map(int, input().split())
    xyp = [tuple(map(int, input().split())) for _ in range(n)]
    xc, yc, _ = zip(*xyp)
    xc, yc = sorted(set(xc)), sorted(set(yc))
    pt = [[0] * len(yc) for _ in xc]
    for x, y, p in xyp:
        x, y = bisect_left(xc, x), bisect_left(yc, y)
        pt[x][y] = p
    s = [[0] * (len(yc) + 1) for _ in range(len(xc) + 1)]
    c = [[0] * (len(yc) + 1) for _ in range(len(xc) + 1)]
    for i in range(len(xc)):
        for j in range(len(yc)):
            s[i + 1][j + 1] = pt[i][j] + s[i + 1][j] + s[i][j + 1] - s[i][j]
            c[i + 1][j + 1] = (1 if pt[i][j] > 0 else 0) + c[i + 1][j] + c[i][j + 1] - c[i][j]

    def ss(a, sx, ex, sy, ey):
        return a[ex][ey] - a[sx][ey] - a[ex][sy] + a[sx][sy]

    ans = 0

    for u in range(len(xc)):
        for d in range(u + 1, len(xc) + 1):
            r = 0
            for l in range(0, len(yc)):
                while r < len(yc) and ss(s, u, d, l, r + 1) <= b:
                    r += 1
                ans = max(ans, ss(c, u, d, l, r))

    return ans


def _start():
    ret = main()

    if ret is not None:
        if isinstance(ret, List) or isinstance(ret, Tuple):
            print(*ret)
        else:
            print(ret)


if __name__ == '__main__':
    _start()
0