結果

問題 No.866 レベルKの正方形
ユーザー fine
提出日時 2019-08-17 00:41:02
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3,103 ms / 6,000 ms
コード長 2,099 bytes
コンパイル時間 4,033 ms
コンパイル使用メモリ 195,212 KB
最終ジャッジ日時 2025-01-07 13:10:57
ジャッジサーバーID
(参考情報)
judge3 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int cnt[2001][2001][26];
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int h, w, K;
cin >> h >> w >> K;
for (int i = 0; i < h; i++) {
string s;
cin >> s;
for (int j = 0; j < w; j++) {
for (int k = 0; k < 26; k++) {
cnt[i + 1][j + 1][k] = cnt[i + 1][j][k];
}
cnt[i + 1][j + 1][s[j] - 'a']++;
}
}
for (int i = 1; i <= h; i++) {
for (int j = 0; j <= w; j++) {
for (int k = 0; k < 26; k++) {
cnt[i][j][k] += cnt[i - 1][j][k];
}
}
}
ll ans = 0;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
int sz = min(i + 1, j + 1);
int ng = 0, ok = sz + 1;
while (ok - ng > 1) {
int mid = (ok + ng) / 2;
int val = 0;
for (int k = 0; k < 26; k++) {
val += bool(cnt[i + 1][j + 1][k] + cnt[i + 1 - mid][j + 1 - mid][k] - cnt[i + 1][j + 1 - mid][k] - cnt[i + 1 - mid][j + 1][k]);;
}
if (val >= K) {
ok = mid;
} else {
ng = mid;
}
}
if (ok <= 0 || ok > sz) continue;
int ng2 = sz + 1, ok2 = -1;
while (ng2 - ok2 > 1) {
int mid = (ok2 + ng2) / 2;
int val = 0;
for (int k = 0; k < 26; k++) {
val += bool(cnt[i + 1][j + 1][k] + cnt[i + 1 - mid][j + 1 - mid][k] - cnt[i + 1][j + 1 - mid][k] - cnt[i + 1 - mid][j + 1][k]);;
}
if (val <= K) {
ok2 = mid;
} else {
ng2 = mid;
}
}
if (ok2 <= 0 || ok2 > sz || ok > ok2) continue;
ans += ok2 - ok + 1;
//cerr << i << " " << j << ": " << ok << " " << ok2 << endl;
}
}
cout << ans << "\n";
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0