結果
問題 |
No.1490 スライムと爆弾
|
ユーザー |
|
提出日時 | 2025-07-06 00:25:42 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 574 ms / 2,000 ms |
コード長 | 1,684 bytes |
コンパイル時間 | 381 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 158,880 KB |
最終ジャッジ日時 | 2025-07-06 00:25:53 |
合計ジャッジ時間 | 10,642 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
## https://yukicoder.me/problems/no/1490 import math def main(): H, W, N, M = map(int, input().split()) tulr = [] for _ in range(N): t, u, l, r,a = map(int, input().split()) tulr.append((t - 1, u - 1, l -1, r - 1, a)) bombs = [] for _ in range(M): x, y ,b, c = map(int, input().split()) bombs.append((x - 1, y - 1, b, c)) # 2次元imos法でそのセルが受ける爆風によるダメージを算出 cells = [[0] * (W + 1) for _ in range(H + 1)] for x, y, b, c in bombs: v00 = (max(0, x - b), max(0, y - b)) v10 = (min(H - 1, x + b), max(0, y - b)) v01 = (max(0, x - b), min(W - 1, y + b)) v11 = (min(H - 1, x + b), min(W - 1, y + b)) cells[v00[0]][v00[1]] += c cells[v10[0] + 1][v10[1]] -= c cells[v01[0]][v01[1] + 1] -= c cells[v11[0] + 1][v11[1] + 1] += c for h in range(H + 1): row = 0 for w in range(W +1): row += cells[h][w] cells[h][w] = row for w in range(W + 1): col = 0 for h in range(H + 1): col += cells[h][w] cells[h][w] = col # 累積和 cum_cells = [[0] * (W + 1) for _ in range(H + 1)] for h in range(H): row = 0 for w in range(W): row += cells[h][w] cum_cells[h + 1][w + 1] = row + cum_cells[h][w + 1] answer = 0 for t, u, l, r, a in tulr: damage = cum_cells[u + 1][r + 1] - cum_cells[t][r + 1] - cum_cells[u + 1][l] + cum_cells[t][l] if damage < a: answer += 1 print(answer) if __name__ == "__main__": main()