結果

問題 No.60 魔法少女
コンテスト
ユーザー strangerxxx
提出日時 2021-06-12 03:13:16
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 1,599 ms / 5,000 ms
コード長 1,594 bytes
コンパイル時間 86 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 148,096 KB
最終ジャッジ日時 2024-12-15 07:43:35
合計ジャッジ時間 17,673 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def resolve():
    import sys
    input = sys.stdin.readline
    n, k = map(int, input().split())
    enemies = [list(map(int, input().split())) for _ in range(n)]
    imos = Imos2d(1501, 1501)
    for _ in range(k):
        x, y, w, h, d = map(int, input().split())
        imos.add(y + 500, x + 500, y + h + 500, x + w + 500, d)
    damage = imos.get()
    ans = 0
    for x, y, hp in enemies:
        ans += max(hp - damage[y + 500][x + 500], 0)
    print(ans)


class Imos2d():
    """
    0次2次元いもす法

    Parameters
    ----------
    h : int
        配列の高さ(yの幅)
    w : int
        配列の幅(xの幅)
    default
        リストの初期値
    """

    def __init__(self, h: int, w: int, default=0):
        self.h = h
        self.w = w
        self.data = [[default] * (w + 1) for _ in range(h + 1)]

    def add(self, start_y, start_x, end_y, end_x, value=1):
        # 区間[(start_x, start_y), (end_x, end_y)]にvalueを加算する
        self.data[start_y][start_x] += value
        self.data[start_y][end_x + 1] -= value
        self.data[end_y + 1][start_x] -= value
        self.data[end_y + 1][end_x + 1] += value

    def get(self):
        # 縦横に累積和を計算し取得する
        res = [[0] * self.w for _ in range(self.h)]
        for h in range(self.h):
            for w in range(self.w):
                res[h][w] = res[h][w - 1] + self.data[h][w]
        for w in range(self.w):
            for h in range(1, self.h):
                res[h][w] += res[h - 1][w]
        return res


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