verify/aoj-DPL_3_B-largest_rectangle.test.cpp

• View this file on GitHub
• Last update: 2025-07-03 00:41:25+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/3/DPL_3_B

Depends on

• 最大長方形問題 (algorithm/Others/largest_rectangle.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/3/DPL_3_B"

#include <algorithm>
#include <iostream>
#include <vector>

#include "../algorithm/Others/largest_rectangle.hpp"

int main() {
    int h, w;
    std::cin >> h >> w;

    std::vector c(h, std::vector<char>(w));
    for(int i = 0; i < h; ++i) {
        for(int j = 0; j < w; ++j) std::cin >> c[i][j];
    }

    int ans = 0;
    std::vector<int> height(w, 0);
    for(int i = 0; i < h; ++i) {
        for(int j = 0; j < w; ++j) {
            if(c[i][j] == '0') height[j]++;
            else height[j] = 0;
        }

        auto &&ranges = algorithm::largest_rectangle(height);
        for(int j = 0; j < w; ++j) {
            const auto &[l, r] = ranges[j];
            auto tmp = height[j] * (r - l);
            ans = std::max(ans, tmp);
        }
    }

    std::cout << ans << std::endl;
}

#line 1 "verify/aoj-DPL_3_B-largest_rectangle.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/3/DPL_3_B"

#include <algorithm>
#include <iostream>
#include <vector>

#line 1 "algorithm/Others/largest_rectangle.hpp"



/**
 * @brief 最大長方形問題
 * @docs docs/Others/largest_rectangle.md
 */

#include <functional>
#include <stack>
#include <utility>
#line 13 "algorithm/Others/largest_rectangle.hpp"

namespace algorithm {

// 最大長方形問題．
// 各iにおいて，comp(H[i], H[] within [l,r))==true となるiを含む最大区間[l,r)を求める．O(N).
template <typename Type, class Compare = std::function<bool(const Type &, const Type &)> >
std::vector<std::pair<int, int> > largest_rectangle(
    const std::vector<Type> &h,
    const Compare &comp = [](const Type &a, const Type &b) -> bool { return a <= b; }) {
    const int n = h.size();
    std::vector<std::pair<int, int> > res(n, {0, n});  // res[i]:=(pair of [l,r)).
    std::stack<std::pair<Type, int> > st;
    // left side.
    for(int i = 0; i < n; ++i) {
        while(!st.empty() and comp(h[i], st.top().first)) st.pop();
        if(!st.empty()) res[i].first = st.top().second + 1;
        st.push({h[i], i});
    }
    // right side.
    st = std::stack<std::pair<Type, int> >();
    for(int i = n - 1; i >= 0; --i) {
        while(!st.empty() and comp(h[i], st.top().first)) st.pop();
        if(!st.empty()) res[i].second = st.top().second;
        st.push({h[i], i});
    }
    return res;
}

}  // namespace algorithm


#line 8 "verify/aoj-DPL_3_B-largest_rectangle.test.cpp"

int main() {
    int h, w;
    std::cin >> h >> w;

    std::vector c(h, std::vector<char>(w));
    for(int i = 0; i < h; ++i) {
        for(int j = 0; j < w; ++j) std::cin >> c[i][j];
    }

    int ans = 0;
    std::vector<int> height(w, 0);
    for(int i = 0; i < h; ++i) {
        for(int j = 0; j < w; ++j) {
            if(c[i][j] == '0') height[j]++;
            else height[j] = 0;
        }

        auto &&ranges = algorithm::largest_rectangle(height);
        for(int j = 0; j < w; ++j) {
            const auto &[l, r] = ranges[j];
            auto tmp = height[j] * (r - l);
            ans = std::max(ans, tmp);
        }
    }

    std::cout << ans << std::endl;
}

Back to top page