結果
問題 | No.866 レベルKの正方形 |
ユーザー |
👑 ![]() |
提出日時 | 2019-08-17 16:42:04 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,165 ms / 6,000 ms |
コード長 | 1,742 bytes |
コンパイル時間 | 1,777 ms |
コンパイル使用メモリ | 126,620 KB |
最終ジャッジ日時 | 2025-01-07 13:32:42 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
#include <algorithm>#include <bitset>#include <cassert>#include <cctype>#include <chrono>#define _USE_MATH_DEFINES#include <cmath>#include <cstdio>#include <cstring>#include <ctime>#include <deque>#include <functional>#include <iostream>#include <iterator>#include <map>#include <queue>#include <random>#include <set>#include <sstream>#include <string>#include <tuple>#include <utility>#include <vector>using namespace std;#define FOR(i,m,n) for(int i=(m);i<(n);++i)#define REP(i,n) FOR(i,0,n)#define ALL(v) (v).begin(),(v).end()const int INF = 0x3f3f3f3f;const long long LINF = 0x3f3f3f3f3f3f3f3fLL;const double EPS = 1e-8;const int MOD = 1000000007; // 998244353;const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};/*-------------------------------------------------*/int dp[27][2000][2000];int main() {cin.tie(0); ios::sync_with_stdio(false);// freopen("input.txt", "r", stdin);int h, w, K; cin >> h >> w >> K;vector<string> c(h); REP(i, h) cin >> c[i];for (int i = h - 1; i >= 0; --i) for (int j = w - 1; j >= 0; --j) {REP(k, 27) {if (c[i][j] - 'a' == k) {dp[c[i][j] - 'a'][i][j] = 1;} else {dp[k][i][j] = min(h - i, w - j) + 1;if (i + 1 < h) dp[k][i][j] = min(dp[k][i][j], dp[k][i + 1][j] + 1);if (j + 1 < w) dp[k][i][j] = min(dp[k][i][j], dp[k][i][j + 1] + 1);if (i + 1 < h && j + 1 < w) dp[k][i][j] = min(dp[k][i][j], dp[k][i + 1][j + 1] + 1);}}}long long ans = 0;REP(i, h) REP(j, w) {vector<int> a(27);REP(k, 27) a[k] = dp[k][i][j];sort(ALL(a));ans += a[K] - a[K - 1];}cout << ans << '\n';return 0;}