結果
問題 | No.866 レベルKの正方形 |
ユーザー |
![]() |
提出日時 | 2019-08-22 03:54:44 |
言語 | C++11 (gcc 13.3.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,396 bytes |
コンパイル時間 | 1,165 ms |
コンパイル使用メモリ | 63,520 KB |
実行使用メモリ | 450,944 KB |
最終ジャッジ日時 | 2024-10-11 01:15:01 |
合計ジャッジ時間 | 9,474 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 14 TLE * 8 |
ソースコード
#include <iostream>#include <stdio.h>#include <algorithm>#include <vector>#define llint long long#define inf 1000000000using namespace std;int h, w, k;int sum[2005][2005];char c[2005][2005];int dp[2005][2005];int vec[2005][2005][26];int get(int x, int y, int k){return sum[x+k][y+k]-sum[x+k][y-1]-sum[x-1][y+k]+sum[x-1][y-1];}int main(void){ios::sync_with_stdio(0);cin.tie(0);cin >> h >> w >> k;for(int y = 1; y <= h; y++){for(int x = 1; x <= w; x++){cin >> c[x][y];}}for(int x = 1; x <= w+1; x++) dp[x][h+1] = inf;for(int y = 1; y <= h+1; y++) dp[w+1][y] = inf;for(int i = 0; i < 26; i++){for(int x = 1; x <= w; x++){for(int y = 1; y <= h; y++){sum[x][y] = sum[x-1][y]+sum[x][y-1]-sum[x-1][y-1];if(c[x][y] == i+'a') sum[x][y]++;}}for(int y = h; y >= 1; y--){for(int x = w; x >= 1; x--){dp[x][y] = min(dp[x+1][y], dp[x][y+1]);if(c[x][y] == i+'a') dp[x][y] = 0;if(dp[x][y] <= min(w-x, h-y)){if(get(x, y, dp[x][y]) == 0) dp[x][y]++;}vec[x][y][i] = dp[x][y];}}}llint ans = 0;for(int x = 1; x <= w; x++){for(int y = 1; y <= h; y++){sort(vec[x][y], vec[x][y]+26);if(vec[x][y][k-1] >= inf) continue;if(k >= 26 || vec[x][y][k] >= inf) ans += min(w-x, h-y)+1;else ans += vec[x][y][k];ans -= vec[x][y][k-1];}}cout << ans << endl;return 0;}