結果

問題 No.60 魔法少女
ユーザー strangerxxxstrangerxxx
提出日時 2021-06-12 03:13:16
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 1,616 ms / 5,000 ms
コード長 1,594 bytes
コンパイル時間 632 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 147,968 KB
最終ジャッジ日時 2024-05-08 23:44:15
合計ジャッジ時間 18,700 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 616 ms
46,208 KB
testcase_01 AC 622 ms
46,080 KB
testcase_02 AC 614 ms
46,080 KB
testcase_03 AC 647 ms
58,112 KB
testcase_04 AC 1,361 ms
127,744 KB
testcase_05 AC 1,335 ms
139,520 KB
testcase_06 AC 1,592 ms
146,176 KB
testcase_07 AC 1,413 ms
138,368 KB
testcase_08 AC 1,247 ms
131,840 KB
testcase_09 AC 1,077 ms
121,216 KB
testcase_10 AC 1,549 ms
145,536 KB
testcase_11 AC 834 ms
108,544 KB
testcase_12 AC 1,216 ms
131,712 KB
testcase_13 AC 1,616 ms
147,968 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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