結果
問題 | No.440 2次元チワワ問題 |
ユーザー | tnakao0123 |
提出日時 | 2016-11-03 19:32:49 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 530 ms / 5,000 ms |
コード長 | 1,860 bytes |
コンパイル時間 | 644 ms |
コンパイル使用メモリ | 84,952 KB |
実行使用メモリ | 492,972 KB |
最終ジャッジ日時 | 2023-08-16 13:21:29 |
合計ジャッジ時間 | 7,728 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,900 KB |
testcase_01 | AC | 3 ms
9,984 KB |
testcase_02 | AC | 3 ms
10,016 KB |
testcase_03 | AC | 3 ms
8,060 KB |
testcase_04 | AC | 19 ms
84,100 KB |
testcase_05 | AC | 13 ms
57,488 KB |
testcase_06 | AC | 9 ms
36,796 KB |
testcase_07 | AC | 74 ms
248,740 KB |
testcase_08 | AC | 101 ms
271,260 KB |
testcase_09 | AC | 268 ms
364,788 KB |
testcase_10 | AC | 92 ms
281,820 KB |
testcase_11 | AC | 56 ms
217,916 KB |
testcase_12 | AC | 102 ms
257,220 KB |
testcase_13 | AC | 300 ms
390,528 KB |
testcase_14 | AC | 16 ms
63,576 KB |
testcase_15 | AC | 340 ms
411,020 KB |
testcase_16 | AC | 12 ms
20,560 KB |
testcase_17 | AC | 530 ms
492,776 KB |
testcase_18 | AC | 435 ms
492,772 KB |
testcase_19 | AC | 456 ms
492,972 KB |
testcase_20 | AC | 474 ms
492,768 KB |
testcase_21 | AC | 429 ms
492,748 KB |
testcase_22 | AC | 404 ms
492,796 KB |
testcase_23 | AC | 387 ms
492,956 KB |
testcase_24 | AC | 454 ms
492,776 KB |
testcase_25 | AC | 418 ms
492,920 KB |
ソースコード
/* -*- coding: utf-8 -*- * * 440.cc: No.440 2次元チワワ問題 - yukicoder */ #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<string> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<queue> #include<deque> #include<algorithm> #include<numeric> #include<utility> #include<complex> #include<functional> using namespace std; /* constant */ const int MAX_H = 500; const int MAX_N = 10000; /* typedef */ typedef long long ll; /* global variables */ string brds[MAX_N]; int y0s[MAX_N], x0s[MAX_N], y1s[MAX_N], x1s[MAX_N]; ll ans[MAX_N]; int dp[MAX_H][MAX_H][MAX_H]; /* subroutines */ /* main */ int main() { int h, w; cin >> h >> w; for (int y = 0; y < h; y++) cin >> brds[y]; int n; cin >> n; for (int i = 0; i < n; i++) { cin >> y0s[i] >> x0s[i] >> y1s[i] >> x1s[i]; y0s[i]--, x0s[i]--, y1s[i]--, x1s[i]--; } for (int y = 0; y < h; y++) for (int x0 = 0; x0 < w; x0++) { int cn = 0, wn = 0; int ww = 0, cw = 0; int cww = 0, wwc = 0; for (int x1 = x0; x1 < w; x1++) { if (brds[y][x1] == 'c') wwc += ww, cn++; else cww += cw, ww += wn, cw += cn, wn++; dp[y][x0][x1] = cww + wwc; } } for (int i = 0; i < n; i++) for (int y = y0s[i]; y <= y1s[i]; y++) ans[i] += dp[y][x0s[i]][x1s[i]]; for (int x = 0; x < w; x++) for (int y0 = 0; y0 < h; y0++) { int cn = 0, wn = 0; int ww = 0, cw = 0; int cww = 0, wwc = 0; for (int y1 = y0; y1 < h; y1++) { if (brds[y1][x] == 'c') wwc += ww, cn++; else cww += cw, ww += wn, cw += cn, wn++; dp[x][y0][y1] = cww + wwc; } } for (int i = 0; i < n; i++) for (int x = x0s[i]; x <= x1s[i]; x++) ans[i] += dp[x][y0s[i]][y1s[i]]; for (int i = 0; i < n; i++) printf("%lld\n", ans[i]); return 0; }