test/rectangle/MaximumRectangle-1.test.cpp

• View this file on GitHub
• Last update: 2023-08-19 07:15:04+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_B

Depends on

• MaximumRectangle - 最大長方形 (lib/17-rectangle/MaximumRectangle.cpp)

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_B"

#include <vector>
#include <iostream>
#include <stack>
using namespace std;
#include "../../lib/17-rectangle/MaximumRectangle.cpp"

int main(void){
    cin.tie(0);ios::sync_with_stdio(false);
    int H,W; cin >> H >> W;
    vector<vector<long long>> c(H,vector<long long>(W,0));
    vector<vector<long long>> s(H,vector<long long>(W,0));    
    for(int i=0;i<H;++i) {
        for(int j=0;j<W;++j) {
            cin >> c[i][j];
        }
    }
    for(int j=0;j<W;++j) {
        s[0][j]=(!c[0][j]);
        for(int i=1;i<H;++i) {
            if(c[i][j]) s[i][j]=0;
            else s[i][j]=s[i-1][j]+1;
        }
    }
    long long ans = 0;
    for(int i=0;i<H;++i) {
        ans=max(ans,MaximumRectangle(s[i]));
    }
    cout << ans << endl;
	return 0;
}

#line 1 "test/rectangle/MaximumRectangle-1.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_B"

#include <vector>
#include <iostream>
#include <stack>
using namespace std;
#line 1 "lib/17-rectangle/MaximumRectangle.cpp"
/*
 * @title MaximumRectangle - 最大長方形
 * @docs md/rectangle/MaximumRectangle.md
 */
long long MaximumRectangle(vector<long long> ar){
	ar.push_back(0);
	stack<pair<long long,long long>> st;
	long long res = 0;
	for(long long r = 0; r < ar.size(); ++r){
		long long vr = ar[r];
		long long x = r;		
		while(st.size() && st.top().first > vr) {
			auto [vl, l] = st.top(); st.pop();
			x = l;
			res = max(res,vl*(r - l));
		}
		if(st.empty() || (st.size() && st.top().first < vr)) st.push({vr,x});
	}
	return res;
}
#line 8 "test/rectangle/MaximumRectangle-1.test.cpp"

int main(void){
    cin.tie(0);ios::sync_with_stdio(false);
    int H,W; cin >> H >> W;
    vector<vector<long long>> c(H,vector<long long>(W,0));
    vector<vector<long long>> s(H,vector<long long>(W,0));    
    for(int i=0;i<H;++i) {
        for(int j=0;j<W;++j) {
            cin >> c[i][j];
        }
    }
    for(int j=0;j<W;++j) {
        s[0][j]=(!c[0][j]);
        for(int i=1;i<H;++i) {
            if(c[i][j]) s[i][j]=0;
            else s[i][j]=s[i-1][j]+1;
        }
    }
    long long ans = 0;
    for(int i=0;i<H;++i) {
        ans=max(ans,MaximumRectangle(s[i]));
    }
    cout << ans << endl;
	return 0;
}

Back to top page