結果
問題 | No.866 レベルKの正方形 |
ユーザー |
![]() |
提出日時 | 2024-04-14 14:28:45 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,334 ms / 6,000 ms |
コード長 | 1,569 bytes |
コンパイル時間 | 1,256 ms |
コンパイル使用メモリ | 111,988 KB |
実行使用メモリ | 19,456 KB |
最終ジャッジ日時 | 2024-10-03 13:34:26 |
合計ジャッジ時間 | 28,018 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>#include <limits>using namespace std;int main() {int H, W, K;cin >> H >> W >> K;vector<vector<int>> A(H, vector<int>(W));for (int h = 0; h < H; ++h) {string row;cin >> row;for (int w = 0; w < W; ++w) {A[h][w] = row[w] - 'a';}}const int inf = 1<<30;vector<int> dp(26 * W, inf);long long ans = 0;for (int h = 0; h < H; ++h) {vector<int> prev = dp;fill(dp.begin(), dp.end(), inf);for (int w = 0; w < W; ++w) {for (int a = 0; a < 26; ++a) {if (A[h][w] == a) {dp[a * W + w] = 0;}if (h > 0) {dp[a * W + w] = min(dp[a * W + w], prev[a * W + w] + 1);}if (w > 0) {dp[a * W + w] = min(dp[a * W + w], dp[a * W + w - 1] + 1);}if (h > 0 && w > 0) {dp[a * W + w] = min(dp[a * W + w], prev[a * W + w - 1] + 1);}}vector<int> idx;for (int a = 0; a < 26; ++a) {if (dp[a * W + w] <= min(h, w)) {idx.push_back(dp[a * W + w]);}}idx.push_back(min(h, w) + 1);if (idx.size() > K) {sort(idx.begin(), idx.end());ans += idx[K] - idx[K - 1];}}}cout << ans << endl;return 0;}