結果
問題 | No.866 レベルKの正方形 |
ユーザー |
![]() |
提出日時 | 2019-08-17 17:12:15 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3,531 ms / 6,000 ms |
コード長 | 1,246 bytes |
コンパイル時間 | 1,157 ms |
コンパイル使用メモリ | 100,768 KB |
実行使用メモリ | 433,420 KB |
最終ジャッジ日時 | 2024-09-24 20:11:45 |
合計ジャッジ時間 | 43,498 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
#include <iostream>#include <algorithm>#include <string>#include <vector>#include <cmath>#include <map>#include <queue>#include <iomanip>#include <set>#define MOD 1000000007#define mkp make_pairtypedef long long ll;using namespace std;int H,W,K;string S[2001];int c[2001][2001];int dp[26][2001][2001];void chmin(int &a,int b){if(a>b) a=b;}int main(){cin>>H>>W>>K;for(int i=0;i<H;i++) cin>>S[i];for(int i=0;i<H;i++){for(int j=0;j<W;j++){c[i][j]=S[i][j]-'a';}}for(int a=0;a<26;a++) for(int i=0;i<H;i++) for(int j=0;j<W;j++) dp[a][i][j]=min(H-i+1,W-j+1);for(int a=0;a<26;a++){for(int i=H-1;i>=0;i--){for(int j=W-1;j>=0;j--){if(c[i][j]==a) dp[a][i][j]=1;else{if(i+1<H) chmin(dp[a][i][j],dp[a][i+1][j]+1);if(j+1<W) chmin(dp[a][i][j],dp[a][i][j+1]+1);if(i+1<H&&j+1<W) chmin(dp[a][i][j],dp[a][i+1][j+1]+1);}}}}ll ans=0;for(int i=0;i<H;i++){for(int j=0;j<W;j++){vector<int> v;for(int a=0;a<26;a++) v.push_back(dp[a][i][j]);sort(v.begin(),v.end());if(K==26) ans+=min(H-i+1,W-j+1)-v[K-1];else ans+=v[K]-v[K-1];}}cout<<ans<<endl;return 0;}