結果
問題 | No.60 魔法少女 |
ユーザー |
![]() |
提出日時 | 2014-11-09 23:50:26 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 257 ms / 5,000 ms |
コード長 | 1,824 bytes |
コンパイル時間 | 733 ms |
コンパイル使用メモリ | 83,744 KB |
実行使用メモリ | 145,176 KB |
最終ジャッジ日時 | 2024-12-31 09:03:42 |
合計ジャッジ時間 | 3,564 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 10 |
ソースコード
#include <vector> #include <queue> #include <deque> #include <stack> #include <map> #include <set> #include <algorithm> #include <functional> #include <iostream> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <cctype> #include <string> #include <cstring> using namespace std; typedef long long ll; ll field[3000][3000]; ll memo[3000][3000]; int main() { int bias = 1000; memset(field, 0, sizeof(field)); memset(memo, 0, sizeof(memo)); ll n, k; cin >> n >> k; vector <pair<int, int> > vpii; for (int i = 0; i < n; i++) { int x, y, h; cin >> x >> y >> h; x += bias; y += bias; field[x][y] = h; vpii.push_back(make_pair(x, y)); } int minx, miny, maxx, maxy; minx = miny = 1e9; maxx = maxy = -1e9; for (int i = 0; i < k; i++) { int ax, ay, w, h, d; cin >> ax >> ay >> w >> h >> d; ax += bias; ay += bias; memo[ax][ay] += d; memo[ax+w+1][ay] -= d; memo[ax][ay+h+1] -= d; memo[ax+w+1][ay+h+1] += d; minx = min(minx, ax); miny = min(miny, ay); maxx = max(maxx, ax+w+1); maxy = max(maxy, ay+h+1); } for (int i = minx+1; i <= maxx; i++) { for (int j = miny; j <= maxy; j++) { memo[i][j] += memo[i-1][j]; } } for (int i = miny+1; i <= maxy; i++) { for (int j = minx; j <= maxx; j++) { memo[j][i] += memo[j][i-1]; } } // for (int i = miny; i <= maxy; i++) { // for (int j = minx; j <= maxx; j++) { // cout << memo[j][i]; // } // cout << endl; // } ll ans = 0; for (int i = 0; i < vpii.size(); i++) { int px = vpii[i].first, py = vpii[i].second; if (field[px][py]-memo[px][py] > 0) ans += ll(field[px][py]-memo[px][py]); } cout << ans << endl; }