結果
問題 | No.866 レベルKの正方形 |
ユーザー |
![]() |
提出日時 | 2019-08-16 21:52:56 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,546 bytes |
コンパイル時間 | 276 ms |
コンパイル使用メモリ | 34,432 KB |
実行使用メモリ | 423,240 KB |
最終ジャッジ日時 | 2024-09-22 16:02:59 |
合計ジャッジ時間 | 15,978 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 3 |
other | AC * 10 TLE * 3 -- * 9 |
ソースコード
#include <cstdio>#pragma warning(disable : 4996)int H, W, c[26]; char S[2009][2009]; short xsum[26][2009][2009], ysum[26][2009][2009];long long solve(int K) {long long ans = 0;for (int i = 0; i < H; ++i) {int sz = 0, cnt = 0;for (int j = 0; j < W; ++j) {while (cnt < K && i + sz < H && j + sz < W) {for (int k = 0; k < 26; ++k) {short delta = 0;delta += xsum[k][i + sz][j + sz + 1] - xsum[k][i + sz][j];delta += ysum[k][i + sz][j + sz] - ysum[k][i][j + sz];if (delta > 0 && c[k] == 0) ++cnt;c[k] += delta;}++sz;}if (sz != 0) {ans += sz - 1;if (cnt < K) ++ans;}if (sz > 0) {--sz;for (int k = 0; k < 26; ++k) {short delta = 0;delta += xsum[k][i + sz][j + sz + 1] - xsum[k][i + sz][j];delta += ysum[k][i + sz][j] - ysum[k][i][j];c[k] -= delta;if (delta > 0 && c[k] == 0) --cnt;}}}}return ans;}int main() {int K;scanf("%d %d %d", &H, &W, &K);for (int i = 0; i < H; ++i) scanf("%s", S[i]);for (int i = 0; i < H; ++i) {for (int j = 0; j < W; ++j) {++xsum[S[i][j] - 'a'][i][j + 1];++ysum[S[i][j] - 'a'][i + 1][j];}}for (int i = 0; i < 26; ++i) {for (int j = 0; j < H; ++j) {for (int k = 0; k < W; ++k) {xsum[i][j][k + 1] += xsum[i][j][k];}}for (int j = 0; j < W; ++j) {for (int k = 0; k < H; ++k) {ysum[i][k + 1][j] += ysum[i][k][j];}}}long long res1 = solve(K);long long res2 = solve(K + 1);printf("%lld\n", res2 - res1);return 0;}