結果
問題 |
No.165 四角で囲え!
|
ユーザー |
![]() |
提出日時 | 2025-03-19 20:31:27 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 3,132 ms / 5,000 ms |
コード長 | 3,100 bytes |
コンパイル時間 | 404 ms |
コンパイル使用メモリ | 82,192 KB |
実行使用メモリ | 88,444 KB |
最終ジャッジ日時 | 2025-03-19 20:31:58 |
合計ジャッジ時間 | 26,183 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 19 |
ソースコード
import sys input = sys.stdin.readline def cumsum2(a: list[list]): rows = len(a) cols = len(a[0]) t = [[0] * cols for _ in range(rows)] for i in range(rows): for j in range(cols): t[i][j] = a[i][j] if i > 0: t[i][j] += t[i-1][j] if j > 0: t[i][j] += t[i][j-1] if i > 0 and j > 0: t[i][j] -= t[i-1][j-1] def f(sr, sc, tr, tc): s = t[tr][tc] if sr > 0: s -= t[sr-1][tc] if sc > 0: s -= t[tr][sc-1] if sr > 0 and sc > 0: s += t[sr-1][sc-1] return s return f class Compression: def __init__(self, iterable): self.vs = sorted(set(iterable)) self.n = len(self.vs) self.v2i = {} for i, val in enumerate(self.vs): self.v2i[val] = i def __len__(self): return self.n def index(self, val): """val のインデックスを返す""" return self.v2i[val] def value(self, index): """インデックスに対応する値を返す""" return self.vs[index] from collections import defaultdict from itertools import accumulate, combinations def accum(a: list): acc = list(accumulate(a)) return lambda l, r: acc[r] - (acc[l-1] if l > 0 else 0) def shakutori(a: list, can_expand, expand, shrink, identity): n = len(a) res = identity() hi = -1 for lo in range(n): if lo > hi: hi = lo - 1 res = identity() # 必要な分だけ伸ばす while hi+1 < n and can_expand(res, a[hi+1]): res = expand(res, a[hi+1]) hi += 1 if lo <= hi: yield res, lo, hi res = shrink(res, a[lo]) # lo をひとつ進める # res に x を追加できるか def can_expand(res, x): return res+x <= B # 伸ばす(res に x を追加) def expand(res, x): return res+x # 縮める(res から x を削除) def shrink(res, x): return res-x N, B = map(int, input().split()) ps = [] xset = set() yset = set() for _ in range(N): X, Y, P = map(int, input().split()) ps.append((X, Y, P)) xset.add(X) yset.add(Y) xcomp = Compression(xset) ycomp = Compression(yset) xmax = max([xcomp.index(x) for x in xset]) ymax = max([ycomp.index(y) for y in yset]) g = [[0] * (xmax+1) for _ in range(ymax+1)] t = [[0] * (xmax+1) for _ in range(ymax+1)] for x, y, p in ps: cx = xcomp.index(x) cy = ycomp.index(y) g[cy][cx] += p t[cy][cx] += 1 acc_g = cumsum2(g) acc_t = cumsum2(t) def calc(lx: int, rx: int) -> int: scores = [0] * (ymax+1) pts = [0] * (ymax+1) for y in range(ymax+1): scores[y] = acc_g(y, lx, y, rx) pts[y] = acc_t(y, lx, y, rx) acc_pts = accum(pts) res = 0 for _, lo, hi in shakutori(scores, can_expand, expand, shrink, int): res = max(res, acc_pts(lo, hi)) return res ans = 0 xkeys = sorted([xcomp.index(x) for x in xset]) for i in range(len(xkeys)): for j in range(i, len(xkeys)): l = xkeys[i] r = xkeys[j] ans = max(ans, calc(l, r)) print(ans)