No.60 魔法少女

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 139
作問者 : krotonkroton
3 ProblemId : 123 / 出題時の順位表
問題文最終更新日: 2017-03-01 00:43:22

問題文

魔法少女Madokaは魔女Walpurgisnachtと戦っていた。
Walpurgisnachtは複数の使い魔を使役しているため、短時間ですべての敵にダメージを与えない限り倒せない。
そこでMadokaは範囲に対する攻撃魔法を使用し、効率的に敵を倒そうと考えた。

Walpurgisnachtとその使い魔の座標と体力、Madokaが攻撃した範囲と敵に与えるダメージが与えられるので、
倒せていない敵の残り体力の合計を答えよ。

入力

\(N\) \(K\)
\(X_{1}\) \(Y_{1}\) \({HP}_{1}\)
\(X_{2}\) \(Y_{2}\) \({HP}_{2}\)
\(\ldots\)
\(X_{N}\) \(Y_{N}\) \({HP}_{N}\)
\(AX_{1}\) \(AY_{1}\) \(W_{1}\) \(H_{1}\) \(D_{1}\)
\(AX_{2}\) \(AY_{2}\) \(W_{2}\) \(H_{2}\) \(D_{2}\)
\(\ldots\)
\(AX_{K}\) \(AY_{K}\) \(W_{K}\) \(H_{K}\) \(D_{K}\)

入力はすべて整数で与えられる。

  • \(1 \leq N \leq 100000\) は敵の数を表す。
  • \(1 \leq K \leq 100000\) はMadokaの攻撃回数を表す。
  • \(-500 \leq X_{k}, Y_{k} \leq 500\) は \(k\) 番目の敵の座標を表す。
  • \(1 \leq {HP}_{k} \leq 10000\) は \(k\) 番目の敵の体力を表す。
  • \(-500 \leq AX_{t}, AY_{t} \leq 500\)
  • \(1 \leq W_{t}, H_{t} \leq 500\)
  • \(1 \leq D_{t} \leq 10000\)
  • \(t\) 回目の攻撃では \(AX_{t} \leq X \leq AX_{t} + W_{t}\) かつ \(AY_{t} \leq Y \leq AY_{t} + H_{t}\) を満たすすべての敵に \(D\) のダメージを与える。
  • 同じ座標に複数の敵が存在することはないとする。
  • 同じ攻撃が複数回行われることもある。

出力

敵は体力以上のダメージを受けると倒れるものとし、倒れていない敵の体力の合計を計算し出力せよ。

サンプル

サンプル1
入力
7 2
0 0 1
1 0 1
1 1 2
1 2 1
2 0 1
2 1 1
2 2 1
-1 -1 2 2 1
1 0 1 2 1
出力
0

すべての敵を倒したので残り体力の合計は0。

サンプル2
入力
4 1
1 0 1
1 2 1
2 0 2
2 1 1
-1 -1 3 3 2
出力
0
サンプル3
入力
4 1
1 0 2
1 2 1
2 0 1
2 1 1
-1 0 3 3 1
出力
1
サンプル4
入力
10 10
-444 -456 6808
465 31 3659
-16 103 7545
199 342 7710
374 -206 4493
-15 -286 2504
-287 155 8841
-345 -444 3170
-7 304 9561
-143 -456 279
-349 154 13 268 3811
-40 256 150 80 8822
486 270 394 337 5486
310 -342 92 195 6358
111 -243 209 445 5669
-224 -120 197 31 904
436 -206 50 25 7802
-394 -493 409 229 4934
-388 367 136 14 3866
-79 -157 37 426 1670
出力
35302

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。