#ifdef DEBUG #define _GLIBCXX_DEBUG #endif #pragma GCC optimize("Ofast") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define stdin_filepath "stdin.txt" #define stdout_filepath "stdout.txt" #define stderr_filepath "stderr.txt" #define iostream_untie true #define stdout_precision 10 #define stderr_precision 10 #define rep(i,n) for(int_fast64_t i = 0; i < (int_fast64_t)(n); ++i) #define all(v) begin(v), end(v) #define rall(v) rbegin(v), rend(v) #define fir first #define sec second #define u_map unordered_map #define u_set unordered_set #define l_bnd lower_bound #define u_bnd upper_bound #define emp emplace #define emf emplace_front #define emb emplace_back #define pof pop_front #define pob pop_back #define mkp make_pair #define mkt make_tuple #define popcnt __builtin_popcountll using namespace std; using i64 = int_fast64_t; using pii = pair; using pll = pair; template using heap = priority_queue; template using minheap = priority_queue, greater>; template constexpr T inf = numeric_limits::max() / (T)2 - (T)1234567; constexpr int dx[9] = {1, 0, -1, 0, 1, -1, -1, 1, 0}; constexpr int dy[9] = {0, 1, 0, -1, 1, 1, -1, -1, 0}; namespace execution { std::chrono::system_clock::time_point start, end; void print_elapsed_time() { end = std::chrono::system_clock::now(); std::cerr << "\n----- Exec time : "; std::cerr << std::chrono::duration_cast(end - start).count(); std::cerr << " ms -----\n"; } struct setupper { setupper() { if(iostream_untie) { ios::sync_with_stdio(false); std::cin.tie(nullptr); // std::cout.tie(nullptr); // std::cerr.tie(nullptr); } std::cout << std::fixed << std::setprecision(stdout_precision); std::cerr << std::fixed << std::setprecision(stderr_precision); #ifdef LOCAL if(!freopen(stderr_filepath, "wt", stderr)) { freopen("CON", "wt", stderr); std::cerr << "Failed to open the stderr file\n"; } if(!freopen(stdout_filepath, "wt", stdout)) { freopen("CON", "wt", stdout); std::cerr << "Failed to open the stdout file\n"; } if(!freopen(stdin_filepath, "rt", stdin)) { freopen("CON", "rt", stdin); std::cerr << "Failed to open the stdin file\n"; } atexit(print_elapsed_time); start = std::chrono::system_clock::now(); #endif } } __setupper; } namespace std { template void rsort(RAitr __first, RAitr __last) { sort(__first, __last, greater<>()); } template void hash_combine(size_t &seed, T const &key) { seed ^= hash()(key) + 0x9e3779b9 + (seed << 6) + (seed >> 2); } template struct hash> { size_t operator()(pair const &pr) const { size_t seed = 0; hash_combine(seed,pr.first); hash_combine(seed,pr.second); return seed; } }; template ::value - 1> struct hashval_calc { static void apply(size_t& seed, tuple_t const& t) { hashval_calc::apply(seed, t); hash_combine(seed,get(t)); } }; template struct hashval_calc { static void apply(size_t& seed, tuple_t const& t) { hash_combine(seed,get<0>(t)); } }; template struct hash> { size_t operator()(tuple const& t) const { size_t seed = 0; hashval_calc>::apply(seed,t); return seed; } }; } template istream &operator>> (istream &s, pair &p) { return s >> p.first >> p.second; } template ostream &operator<< (ostream &s, const pair p) { return s << p.first << " " << p.second; } template istream &operator>> (istream &s, vector &v) { for(T &e : v) { s >> e; } return s; } template ostream &operator<< (ostream &s, const vector &v) { for(size_t i = 0; i < v.size(); ++i) { s << (i ? " " : "") << v[i]; } return s; } template struct tupleos { static ostream &apply(ostream &s, const tuple_t &t) { tupleos::apply(s,t); return s << " " << get(t); } }; template struct tupleos { static ostream &apply(ostream &s, const tuple_t &t) { return s << get<0>(t); } }; template ostream &operator<< (ostream &s, const tuple &t) { return tupleos, tuple_size>::value - 1>::apply(s,t); } template <> ostream &operator<< (ostream &s, const tuple<> &t) { return s; } #ifdef DEBUG #define dump(...) cerr << " [ " << __LINE__ << " : " << __FUNCTION__ << " ] " << #__VA_ARGS__ << " : ", dump_func(__VA_ARGS__) #else #define dump(...) #endif template void dump_func(const T &x) { cerr << x << '\n'; } template void dump_func(const T &x, Rest ... rest) { cerr << x << ","; dump_func(rest...); } template void write(const T &x) { cout << x << '\n'; } template void write(const T &x, Rest ... rest) { cout << x << ' '; write(rest...); } void writeln() {} template void writeln(const T &x, Rest ... rest) { cout << x << '\n'; writeln(rest...); } #define esc(...) writeln(__VA_ARGS__), exit(0) template void read(P __first, P __second) { for(P i = __first; i != __second; ++i) cin >> *i; } template bool chmin(T &x, const T &y) { return x > y ? x = y, true : false; } template bool chmax(T &x, const T &y) { return x < y ? x = y, true : false; } template constexpr T minf(const T &x, const T &y) { return min(x,y); } template constexpr T maxf(const T &x, const T &y) { return max(x,y); } constexpr bool odd(int_fast64_t n) { return n & 1; } constexpr bool even(int_fast64_t n) { return (int)odd(n) ^ 1; } constexpr bool bit(int_fast64_t n, int e) { return (n >> e) & 1; } constexpr int_fast64_t mask(int_fast64_t n, int e) { return n & ((1 << e) - 1); } constexpr int_fast64_t ilog(int_fast64_t x, int_fast64_t b = 2) { return x ? 1 + ilog(x / b, b) : -1; } constexpr int_fast64_t gcd(int_fast64_t x, int_fast64_t y) { x = x > 0 ? x : -x, y = y > 0 ? y : -y; while(y) x %= y, x ^= y ^= x ^= y; return x; } constexpr int_fast64_t lcm(int_fast64_t x, int_fast64_t y) { return x ? x / gcd(x, y) * y : 0; } int_fast64_t binry(int_fast64_t ok, int_fast64_t ng, const function &fn) { while (abs(ok - ng) > 1) { int_fast64_t mid = (ok + ng) / 2; (fn(mid) ? ok : ng) = mid; } return ok; } template void init(A (&array)[N], const T &val) { fill((T*)array, (T*)(array + N), val); } template void init(A (&array)[N]) { memset(array, 0, sizeof(array)); } template vector cmprs(const vector &v) { vector tmp = v; vector ret; sort(begin(tmp),end(tmp)); tmp.erase(unique(begin(tmp),end(tmp)), end(tmp)); for(const T &i : v) ret.emplace_back(lower_bound(begin(tmp),end(tmp),i) - begin(tmp)); return ret; } template vector cmprs(const T *__first, const T *__last) { return cmprs(vector(__first, __last)); } void for_subset(int_fast64_t s, const function &fn) { int_fast64_t t = s; do { fn(t); } while((--t &= s) != s); } /* The main code follows. */ signed main() { void solve(); void input(); void init(); int t = 1; #ifdef LOCAL t = 3; // cin >> t; #endif // cin >> t; while(t--) { init(); input(); solve(); } } int h,w,k; int g[26][2005][2005]; void init() { init(g); } void input() { cin>>h>>w>>k; char c; for(int i=0; ij; j++) { cin>>c; g[c-'a'][i+1][j+1]=1; } } } void solve() { for(int i=0; i=j; j++) { int &x=nowl[j]; x=prvl[j-1]+1; while(ckin(i-x,j-x,i,j)>=k) { x--; } int &y=nowu[j]; y=prvu[j-1]+1; while(ckin(i-y,j-y,i,j)>k) { y--; } ans+=y-x; dump(i,j,x,y); } swap(nowl,prvl), swap(nowu,prvu); } write(ans); } int ckin(int a,int b,int c,int d) { int ret=0; for(int i=0; i<26; i++) { ret+=bool(g[i][c][d]-g[i][c][b]-g[i][a][d]+g[i][a][b]); } return ret; }