結果
問題 |
No.866 レベルKの正方形
|
ユーザー |
![]() |
提出日時 | 2019-08-17 13:06:13 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,446 bytes |
コンパイル時間 | 1,563 ms |
コンパイル使用メモリ | 171,496 KB |
実行使用メモリ | 431,564 KB |
最終ジャッジ日時 | 2024-09-24 19:17:52 |
合計ジャッジ時間 | 45,960 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 WA * 3 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long double ld; typedef long long ll; typedef unsigned long long ull; #define endl "\n" #define MP make_pair #define FOR(i,a,b) for(int i=(a);i<=(b);i++) #define FORR(x,arr) for(auto& x:arr) #define PII pair<int, int> #define FI first #define SE second #define ALL(x) (x).begin(), (x).end() const int INF=1<<30; const ll LINF=1LL<<60; const ll mod=1e9+7; const int NIL = -1; template<class T>inline bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; } template<class T>inline bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; } //------------------- int h,w,k; char table[2000+5][2000+5]; int dp[2000+5][2000+5][27]; int base = int('a'); int main(){ cin >> h >> w >> k; ll ans = 0; memset(dp,INF,sizeof(dp)); FOR(i,1,h) FOR(j,1,w){ cin >> table[i][j]; } for(int a=0; a<26;a++){ for(int i=h+1; i>=1; i--){ for(int j=w+1; j>=1; j--){ if(table[i][j] == char(base+a)){ dp[i][j][a] = 1; continue; } dp[i][j][a] = min(dp[i+1][j+1][a], min(dp[i+1][j][a],dp[i][j+1][a]))+1; //dp[i][j][a] = min(dp[i][j][a], min(h+1-i, w+1-j)+1); } } } FOR(i,1,h){ FOR(j,1,w){ sort(dp[i][j], dp[i][j]+26); if(dp[i][j][k-1] >= INF) continue; else if(dp[i][j][k] >= INF){ ans += 1LL* ( min(h+1-i, w+1-j)+1-dp[i][j][k-1]); continue;} ans += 1LL * (dp[i][j][k] - dp[i][j][k-1]); } } cout << ans << endl; return 0; }