結果
問題 |
No.866 レベルKの正方形
|
ユーザー |
|
提出日時 | 2021-05-03 16:33:26 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,157 ms / 6,000 ms |
コード長 | 1,116 bytes |
コンパイル時間 | 1,881 ms |
コンパイル使用メモリ | 196,984 KB |
最終ジャッジ日時 | 2025-01-21 06:17:36 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
#include <bits/stdc++.h> using namespace std; int dp[2001][2001][26]; int calc(int y1, int x1, int n) { int y2 = y1 + n - 1; int x2 = x1 + n - 1; int ret = 0; for (int k = 0; k < 26; k++) if (dp[y2][x2][k] - dp[y2][x1-1][k] - dp[y1-1][x2][k] + dp[y1-1][x1-1][k] > 0) ++ret; return ret; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int h, w, p; cin >> h >> w >> p; vector<string> bd(h); for (int i = 0; i < h; i++) cin >> bd[i]; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { int c = bd[i][j] - 'a'; for (int k = 0; k < 26; k++) dp[i+1][j+1][k] = dp[i+1][j][k] + dp[i][j+1][k] - dp[i][j][k]; dp[i+1][j+1][c]++; } } long long ret = 0; for (int y1 = 1; y1 <= h; y1++) { int l = 1; int r = 1; for (int x1 = 1; x1 <= w; x1++) { int max_n = min(h - y1 + 1, w - x1 + 1); while (l <= max_n && calc(y1, x1, l) < p) l++; while (r <= max_n && calc(y1, x1, r) <= p) r++; ret += r - l; l = max(l-1, 1); r = max(r-1, 1); } } cout << ret << endl; return 0; }