Submission #41008266

---

Source Code Expand

#include <bits/stdc++.h>

namespace {
    using Num = long long int;
}

void solve(std::istream& is, std::ostream& os) {
    using Num = long long int;
    Num h {0};
    Num w {0};
    is >> h >> w;

    std::vector<std::string> strs;
    for(decltype(h) y{0}; y<h; ++y) {
        std::string s {0};
        is >> s;
        strs.push_back(s);
    }

    std::vector<std::vector<Num>> rows(h+2);
    std::vector<std::vector<Num>> columns(w+2);
    for(decltype(h) y{0}; y<=(h+1); ++y) {
        rows[y].push_back(0);
    }

    for(decltype(w) x{0}; x<=(w+1); ++x) {
        columns[x].push_back(0);
    }

    for(decltype(h) y{0}; y<h; ++y) {
        for(decltype(w) x{0}; x<w; ++x) {
            if (strs[y][x] == '#') {
                rows[y+1].push_back(x+1);
                columns[x+1].push_back(y+1);
            }
        }
    }

    for(decltype(h) y{0}; y<=(h+1); ++y) {
        rows[y].push_back(w+1);
    }

    for(decltype(w) x{0}; x<=(w+1); ++x) {
        columns[x].push_back(h+1);
    }

    Num answer {0};
    for(decltype(h) y{1}; y<=h; ++y) {
        for(decltype(w) x{1}; x<=w; ++x) {
            if (strs[y-1][x-1] == '#') {
                continue;
            }

            auto& row = rows.at(y);
            auto it_row = std::upper_bound(row.begin(), row.end(), x);
            auto right = *it_row;
            --it_row;
            auto left = *it_row;
            const Num n_row = right - left - 1;

            auto& column = columns.at(x);
            auto it_column = std::upper_bound(column.begin(), column.end(), y);
            auto bottom = *it_column;
            --it_column;
            auto top = *it_column;
            const Num n_column = bottom - top - 1;

            const auto n = n_row + n_column - 1;
            answer = std::max(answer, n);
        }
    }

    os << answer << "\n";
    return;
}

int main(void) {
    solve(std::cin, std::cout);
    return 0;
}

Submission Info

Judge Result