結果

問題 No.866 レベルKの正方形
ユーザー lam6er
提出日時 2025-04-16 16:48:24
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,090 bytes
コンパイル時間 4,708 ms
コンパイル使用メモリ 82,476 KB
実行使用メモリ 15,652 KB
最終ジャッジ日時 2025-04-16 16:50:54
合計ジャッジ時間 12,822 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 8 TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int H, W, K;
    cin >> H >> W >> K;
    vector<string> grid(H);
    for (int i = 0; i < H; ++i) {
        cin >> grid[i];
    }

    int result = 0;
    int max_size = min(H, W);

    for (int s = 1; s <= max_size; ++s) {
        vector<vector<int>> cnt(W, vector<int>(26, 0));
        vector<vector<bool>> col_has(W, vector<bool>(26, false));

        // Initialize for the first window (i=0)
        for (int j = 0; j < W; ++j) {
            for (int i_row = 0; i_row < s; ++i_row) {
                char c = grid[i_row][j];
                cnt[j][c - 'a']++;
            }
            for (int c = 0; c < 26; ++c) {
                col_has[j][c] = cnt[j][c] > 0;
            }
        }

        for (int i = 0; i <= H - s; ++i) {
            if (i > 0) {
                // Update each column's cnt and col_has
                for (int j = 0; j < W; ++j) {
                    // Remove the top row (i-1)
                    char old_char = grid[i-1][j];
                    cnt[j][old_char - 'a']--;
                    // Add the new bottom row (i + s - 1)
                    char new_char = grid[i + s - 1][j];
                    cnt[j][new_char - 'a']++;

                    // Update col_has for old_char and new_char
                    col_has[j][old_char - 'a'] = cnt[j][old_char - 'a'] > 0;
                    col_has[j][new_char - 'a'] = cnt[j][new_char - 'a'] > 0;
                }
            }

            // Process the sliding window in columns
            vector<int> total(26, 0);
            int unique = 0;

            // Initialize the first s columns
            for (int c = 0; c < 26; ++c) {
                for (int j = 0; j < s; ++j) {
                    if (col_has[j][c]) {
                        total[c]++;
                    }
                }
                if (total[c] > 0) {
                    unique++;
                }
            }

            if (unique == K) {
                result++;
            }

            // Slide the window to the right
            for (int j = 1; j <= W - s; ++j) {
                int left = j - 1;
                int right = j + s - 1;

                // Remove the leftmost column
                for (int c = 0; c < 26; ++c) {
                    if (col_has[left][c]) {
                        total[c]--;
                        if (total[c] == 0) {
                            unique--;
                        }
                    }
                }

                // Add the new rightmost column
                for (int c = 0; c < 26; ++c) {
                    if (col_has[right][c]) {
                        total[c]++;
                        if (total[c] == 1) {
                            unique++;
                        }
                    }
                }

                if (unique == K) {
                    result++;
                }
            }
        }
    }

    cout << result << '\n';

    return 0;
}
0