結果
問題 | No.866 レベルKの正方形 |
ユーザー |
![]() |
提出日時 | 2019-08-16 22:59:55 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,553 bytes |
コンパイル時間 | 8,073 ms |
コンパイル使用メモリ | 267,948 KB |
最終ジャッジ日時 | 2025-01-07 12:43:41 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 TLE * 1 |
ソースコード
#include <bits/stdc++.h>using vi26 = std::vector<std::array<int, 26>>;using vvi26 = std::vector<vi26>;int H, W, K;vvi26 table;int calcLevelK(int, int);bool lowerBound(int, int, int, int);int main(){scanf("%d%d%d", &H, &W, &K);table.resize(H + 1, vi26(W + 1));for (int h{1}; h <= H; h++)for (int w{1}; w <= W; w++){char c;scanf(" %c", &c);table[h][w][c - 'a']++;}for (int h{1}; h <= H; h++)for (int w{1}; w <= W; w++)for (int c{}; c < 26; c++)table[h][w][c] += table[h][w - 1][c];for (int h{1}; h <= H; h++)for (int w{}; w <= W; w++)for (int c{}; c < 26; c++)table[h][w][c] += table[h - 1][w][c];int64_t ans{};for (int h{}; h < H; h++)for (int w{}; w < W; w++)ans += calcLevelK(h, w);printf("%lld\n", ans);return 0;}int calcLevelK(int h, int w){int k_left{}, k_right{std::min(H + 1 - h, W + 1 - w)};while (k_right - k_left > 1){int mid{(k_right + k_left) / 2};if (lowerBound(h, w, mid, K)) k_right = mid;else k_left = mid;}if (k_right == std::min(H + 1 - h, W + 1 - w)) return 0;int k1_left{}, k1_right{std::min(H + 1 - h, W + 1 - w)};while (k1_right - k1_left > 1){int mid{(k1_right + k1_left) / 2};if (lowerBound(h, w, mid, K + 1)) k1_right = mid;else k1_left = mid;}return k1_right - k_right;}bool lowerBound(int h, int w, int size, int k){int level{};for (int c{}; c < 26; c++)if (table[h + size][w + size][c] + table[h][w][c] - table[h][w + size][c] - table[h + size][w][c] > 0)level++;return level >= k;}