結果
問題 | No.866 レベルKの正方形 |
ユーザー |
![]() |
提出日時 | 2019-08-18 14:34:36 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,166 ms / 6,000 ms |
コード長 | 1,108 bytes |
コンパイル時間 | 798 ms |
コンパイル使用メモリ | 71,216 KB |
実行使用メモリ | 441,576 KB |
最終ジャッジ日時 | 2024-10-01 14:04:14 |
合計ジャッジ時間 | 31,624 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
#include <iostream>#include <algorithm>using namespace std;using ll = long long;int h,w,k;int a[2000][2000], r[2001][2001][27];int main() {cin >> h >> w >> k;char c;for(int i=0;i<h;++i) {for(int j=0;j<w;++j) {cin >> c;a[i][j] = int(c - 'a');}}fill_n(r[0][0], 2001*2001*27, 1);for(int i=h-1;i>=0;--i) {for(int j=w-1;j>=0;--j) {for(int ci=0;ci<27;++ci) {if(a[i][j] == ci) {r[i][j][ci] = 1;} else {r[i][j][ci] = min(min(h-i, w-j) + 1, min({r[i+1][j][ci], r[i][j+1][ci], r[i+1][j+1][ci]}) + 1);}}}}ll ans = 0;for(int i=0;i<h;++i) {for(int j=0;j<w;++j) {sort(r[i][j], r[i][j]+26);if(r[i][j][k-1] == 1<<30) continue;if(r[i][j][k] == 1<<30) {ans += min(h-i, w-j) + 1 - r[i][j][k-1];} else {ans += r[i][j][k] - r[i][j][k-1];}}}cout << ans << endl;}