Aizu Online Judge(AOJ)の過去問から、その提出コードの解答例です。
・問題 "Largest Rectangle"
https://onlinejudge.u-aizu.ac.jp/problems/DPL_3_B
・最大長方形
僕が作成、提出したコードは、以下のとおりです。
Aizu Online Judge in C++ #DPL_3_B : Largest Rectangle
/* Aizu Online Judge in C++ #DPL_3_B : Largest Rectangle https://onlinejudge.u-aizu.ac.jp/problems/DPL_3_B 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll h,w,c[1405][1405],ans=0; stack<ll> s; cin>>h>>w; for(ll i=1;i<=h;i++){ for(ll j=1;j<=w;j++){ cin>>c[i][j]; if(c[i][j]){ c[i][j]=0; }else{ c[i][j]=c[i-1][j]+1; } while(!s.empty() && c[i][j]<c[i][s.top()]){ ll num=s.top(); while(!s.empty() && num==s.top()){ s.pop(); } ans=max(ans,c[i][num]*(j-((s.empty()) ? 0 : s.top())-1)); } s.emplace(j); } while(!s.empty()){ ll num=s.top(); s.pop(); ans=max(ans,c[i][num]*(w-((s.empty()) ? 0 : s.top()))); } } cout<<ans<<endl; return 0; }
設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge(AOJ)」です。
http://judge.u-aizu.ac.jp/onlinejudge/