結果
問題 |
No.866 レベルKの正方形
|
ユーザー |
|
提出日時 | 2021-05-03 16:26:43 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,095 bytes |
コンパイル時間 | 1,859 ms |
コンパイル使用メモリ | 196,916 KB |
最終ジャッジ日時 | 2025-01-21 06:17:09 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 TLE * 5 |
ソースコード
#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; 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++; int r = l; while (r <= max_n && calc(y1, x1, r) == p) r++; ret += r - l; l = max(l-1, 1); } } cout << ret << endl; return 0; }