結果
問題 | No.866 レベルKの正方形 |
ユーザー |
![]() |
提出日時 | 2019-08-16 23:49:39 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4,404 ms / 6,000 ms |
コード長 | 4,096 bytes |
コンパイル時間 | 1,063 ms |
コンパイル使用メモリ | 131,964 KB |
実行使用メモリ | 443,008 KB |
最終ジャッジ日時 | 2024-11-30 14:50:28 |
合計ジャッジ時間 | 54,914 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
//#define NDEBUG#include <cstddef>#include <cstdint>#include <iostream>#include <vector>namespace n91 {using i8 = std::int_fast8_t;using i32 = std::int_fast32_t;using i64 = std::int_fast64_t;using u8 = std::uint_fast8_t;using u32 = std::uint_fast32_t;using u64 = std::uint_fast64_t;using isize = std::ptrdiff_t;using usize = std::size_t;constexpr usize operator"" _z(unsigned long long x) noexcept {return static_cast<usize>(x);}class rep {const usize f, l;public:class itr {friend rep;usize i;constexpr itr(const usize x) noexcept : i(x) {}public:void operator++() noexcept { ++i; }constexpr usize operator*() const noexcept { return i; }constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }};constexpr rep(const usize first, const usize last) noexcept: f(first), l(last) {}constexpr itr begin() const noexcept { return itr(f); }constexpr itr end() const noexcept { return itr(l); }};class revrep {const usize f, l;public:class itr {friend revrep;usize i;constexpr itr(usize x) noexcept : i(x) {}public:void operator++() noexcept { --i; }constexpr usize operator*() const noexcept { return i; }constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }};constexpr revrep(usize first, usize last) noexcept : f(--first), l(--last) {}constexpr itr begin() const noexcept { return itr(l); }constexpr itr end() const noexcept { return itr(f); }};template <class T> using vec_alias = std::vector<T>;template <class T> auto md_vec(const usize n, const T &value) {return std::vector<T>(n, value);}template <class... Args> auto md_vec(const usize n, Args... args) {return std::vector<decltype(md_vec(args...))>(n, md_vec(args...));}template <class T> constexpr T difference(const T &a, const T &b) {return a < b ? b - a : a - b;}template <class T> T scan() {T ret;std::cin >> ret;return ret;}} // namespace n91#include <algorithm>#include <array>#include <iostream>#include <utility>namespace n91 {void main_() {const usize h = scan<usize>();const usize w = scan<usize>();const usize k = scan<usize>();auto c = md_vec(h, w, usize());for (auto &v : c) {for (auto &e : v) {e = scan<char>() - 'a';}}auto sum = md_vec(h + 1, w + 1, std::array<std::uint_least32_t, 26_z>({}));for (const auto i : rep(0_z, h)) {for (const auto j : rep(0_z, w)) {sum[i + 1_z][j + 1_z][c[i][j]] += 1_z;}}for (const auto i : rep(0_z, h)) {for (const auto j : rep(0_z, w)) {for (const auto k : rep(0_z, 26_z)) {sum[i + 1_z][j + 1_z][k] += sum[i + 1_z][j][k];}}}for (const auto i : rep(0_z, h)) {for (const auto j : rep(0_z, w)) {for (const auto k : rep(0_z, 26_z)) {sum[i + 1_z][j + 1_z][k] += sum[i][j + 1_z][k];}}}const auto count = [&](const usize xl, const usize xr, const usize yl,const usize yr) {usize ret = 0_z;for (const auto i : rep(0_z, 26_z)) {if ((sum[xl][yl][i] + sum[xr][yr][i] - sum[xl][yr][i] - sum[xr][yl][i]) !=0_z) {++ret;}}return ret;};u64 ans = static_cast<u64>(0);for (const auto xl : rep(0_z, h)) {for (const auto yl : rep(0_z, w)) {const usize maxd = std::min(h - xl, w - yl);usize low = 0_z, high = maxd + 1_z;while (high - low != 1_z) {const usize mid = (low + high) / 2_z;if (count(xl, xl + mid, yl, yl + mid) < k) {low = mid;} else {high = mid;}}const usize lb = high;low = 0_z, high = maxd + 1_z;while (high - low != 1_z) {const usize mid = (low + high) / 2_z;if (count(xl, xl + mid, yl, yl + mid) <= k) {low = mid;} else {high = mid;}}ans += high - lb;}}std::cout << ans << std::endl;}} // namespace n91int main() {n91::main_();return 0;}