結果

問題 No.866 レベルKの正方形
コンテスト
ユーザー WarToks
提出日時 2019-08-16 23:46:38
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,557 bytes
コンパイル時間 1,210 ms
コンパイル使用メモリ 131,392 KB
実行使用メモリ 426,272 KB
最終ジャッジ日時 2024-11-30 14:37:46
合計ジャッジ時間 101,607 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8 TLE * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>
#include <cstring>


#define REP(i, n) for(int (i) = 0; (i) < (n); ++(i))
#define eREP(i, n) for(int (i) = 0; (i) <= (n); ++(i))
#define ALL(TheArray) TheArray.begin(), TheArray.end()

template <class T> inline T& chmax(T& a, T b){return (a < b) ? a = b : a;}
template <class T> inline T& chmin(T& a, T b){return (a > b) ? a = b : a;}

using lli = long long int;

constexpr int ALPHABET = 'z' - 'a' + 1;
std::vector<std::string> S;
std::vector<std::vector<int>> Count[ALPHABET];

int main(void){
    int H, W, k; std::cin >> H >> W >> k;
    S.resize(H); REP(i, H) std::cin >> S[i];

    REP(x, ALPHABET){
        char c = 'a' + x;
        Count[x].resize(H + 1, std::vector<int>(W + 1));
        REP(i, H) REP(j, W) Count[x][i+1][j+1] = (S[i][j] == c) ? 1 : 0;
        REP(i, H+1) Count[x][i][0] = 0;
        REP(j, W+1) Count[x][0][j] = 0;
        REP(i, H+1) REP(j, W) Count[x][i][j+1] += Count[x][i][j];
        REP(j, W+1) REP(i, H) Count[x][i+1][j] += Count[x][i][j];
    }

    lli res = 0;
    REP(i, H){
        REP(j, W){
            int t = 1;
            while(i + t <= H and j + t <= W){
                int cnt = 0;
                REP(x, ALPHABET){
                    if(Count[x][i+t][j+t] - Count[x][i+t][j] - Count[x][i][j+t] + Count[x][i][j] > 0) cnt++;
                    if(cnt > k) break;
                }
                
                if(cnt == k) res++;
                t++;
            }
        }
    }

    std::cout << res << '\n';

    return 0;
}
0