結果
問題 | No.866 レベルKの正方形 |
ユーザー |
|
提出日時 | 2019-08-16 22:17:35 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,376 bytes |
コンパイル時間 | 2,063 ms |
コンパイル使用メモリ | 174,916 KB |
実行使用メモリ | 420,864 KB |
最終ジャッジ日時 | 2024-09-22 17:40:58 |
合計ジャッジ時間 | 10,193 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 3 |
other | AC * 8 TLE * 8 -- * 6 |
ソースコード
#include <bits/stdc++.h>#define rep(i, n) for (int i = 0; i < (n); i++)#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)using namespace std;using ll = long long;char S[2000][2001];int sum[2001][2001][26];int main() {cin.tie(nullptr); ios::sync_with_stdio(false);int H, W, K;scanf("%d %d %d", &H, &W, &K);rep(i, H) scanf("%s", S[i]);rep(i, H) rep(j, W) rep(k, 26) {sum[i+1][j+1][k] = sum[i+1][j][k] + sum[i][j+1][k] - sum[i][j][k] + (S[i][j] - 'a' == k);}vector<int> from_y, from_x;from_y.push_back(0);from_x.push_back(0);rep(i, H-1) from_y.push_back(i+1), from_x.push_back(0);rep(i, W-1) from_y.push_back(0), from_x.push_back(i+1);auto calc = [&](int k, int y1, int y2, int x1, int x2) -> int {return sum[y2][x2][k] - sum[y2][x1][k] - sum[y1][x2][k] + sum[y1][x1][k];};ll ans = 0;rep(u, from_y.size()) {int y = from_y[u];int x = from_x[u];vector<int> ptr(26);for (; y < H && x < W; y++, x++) {rep(k, 26) {while (ptr[k] + from_y[u] <= H && ptr[k] + from_x[u] <= W && calc(k, y, ptr[k] + from_y[u], x, ptr[k] + from_x[u]) == 0) ptr[k]++;}vector<int> tmp(ptr);tmp.push_back(y - from_y[u]);tmp.push_back(min(H - from_y[u], W - from_x[u]) + 1);sort(tmp.begin(), tmp.end());ans += tmp[K+1] - tmp[K];}}cout << ans << endl;}