結果

問題 No.60 魔法少女
ユーザー strangerxxxstrangerxxx
提出日時 2021-06-12 03:13:16
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 1,436 ms / 5,000 ms
コード長 1,594 bytes
コンパイル時間 548 ms
コンパイル使用メモリ 11,064 KB
実行使用メモリ 145,500 KB
最終ジャッジ日時 2023-08-21 18:06:02
合計ジャッジ時間 16,517 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 550 ms
43,760 KB
testcase_01 AC 548 ms
43,752 KB
testcase_02 AC 550 ms
43,696 KB
testcase_03 AC 581 ms
55,676 KB
testcase_04 AC 1,164 ms
125,120 KB
testcase_05 AC 1,153 ms
137,164 KB
testcase_06 AC 1,436 ms
143,716 KB
testcase_07 AC 1,227 ms
135,720 KB
testcase_08 AC 1,075 ms
129,124 KB
testcase_09 AC 932 ms
118,468 KB
testcase_10 AC 1,325 ms
142,960 KB
testcase_11 AC 724 ms
106,036 KB
testcase_12 AC 1,037 ms
129,068 KB
testcase_13 AC 1,404 ms
145,500 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