結果
問題 | No.60 魔法少女 |
ユーザー | sugim48 |
提出日時 | 2014-11-09 23:36:47 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 236 ms / 5,000 ms |
コード長 | 1,612 bytes |
コンパイル時間 | 713 ms |
コンパイル使用メモリ | 90,644 KB |
実行使用メモリ | 69,076 KB |
最終ジャッジ日時 | 2023-08-30 02:50:05 |
合計ジャッジ時間 | 3,695 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 58 ms
65,896 KB |
testcase_01 | AC | 58 ms
65,672 KB |
testcase_02 | AC | 58 ms
65,664 KB |
testcase_03 | AC | 58 ms
65,644 KB |
testcase_04 | AC | 151 ms
67,552 KB |
testcase_05 | AC | 158 ms
67,756 KB |
testcase_06 | AC | 225 ms
69,076 KB |
testcase_07 | AC | 179 ms
68,244 KB |
testcase_08 | AC | 135 ms
67,292 KB |
testcase_09 | AC | 91 ms
66,408 KB |
testcase_10 | AC | 214 ms
68,520 KB |
testcase_11 | AC | 73 ms
65,880 KB |
testcase_12 | AC | 126 ms
66,940 KB |
testcase_13 | AC | 236 ms
68,716 KB |
ソースコード
#define _USE_MATH_DEFINES #include <algorithm> #include <cstdio> #include <fstream> #include <functional> #include <iostream> #include <cfloat> #include <climits> #include <cstring> #include <cmath> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <time.h> #include <vector> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> i_i; typedef pair<ll, int> ll_i; typedef pair<double, int> d_i; typedef pair<ll, ll> ll_ll; typedef pair<double, double> d_d; struct edge { int u, v; ll w; }; ll MOD = 1000000007; ll _MOD = 1000000009; double EPS = 1e-10; int main() { int N, K; cin >> N >> K; vector<int> X(N), Y(N), h(N); for (int i = 0; i < N; i++) { cin >> X[i] >> Y[i] >> h[i]; X[i] += 500; Y[i] += 500; } vector<int> AX(K), AY(K), W(K), H(K), D(K); for (int j = 0; j < K; j++) { cin >> AX[j] >> AY[j] >> W[j] >> H[j] >> D[j]; AX[j] += 500; AY[j] += 500; W[j]++; H[j]++; } vector< vector<ll> > imos(2000, vector<ll>(2000)); for (int j = 0; j < K; j++) { imos[AY[j]][AX[j]] += D[j]; imos[AY[j]][AX[j] + W[j]] -= D[j]; imos[AY[j] + H[j]][AX[j]] -= D[j]; imos[AY[j] + H[j]][AX[j] + W[j]] += D[j]; } vector< vector<ll> > sum(2001, vector<ll>(2001)); for (int y = 1; y <= 2000; y++) for (int x = 1; x <= 2000; x++) sum[y][x] += sum[y][x - 1] + sum[y - 1][x] - sum[y - 1][x - 1] + imos[y - 1][x - 1]; ll ans = 0; for (int i = 0; i < N; i++) ans += max(0LL, h[i] - sum[Y[i] + 1][X[i] + 1]); cout << ans << endl; }