Pagini recente » Cod sursa (job #621776) | Cod sursa (job #133965) | Cod sursa (job #385420) | Cod sursa (job #562053) | Cod sursa (job #1808700)
#include <bits/stdc++.h>
using namespace std;
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
const int nMax = 203;
char s[nMax][nMax], aux[nMax][nMax];
int sum[nMax][nMax], h[nMax];
int St[nMax], Dr[nMax], dpup[nMax], dpdown[nMax];
int ans = 0;
stack <int> Stiva;
int n , m;
inline void Read() {
f >> n >> m;
for(int i = 1; i <= n; i++) {
f >> (s[i] + 1);
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
aux[i][j] = s[i][j];
}
}
}
inline void Prec() {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
sum[i][j] = s[i][j] - '0';
if(sum[i][j] == 0) {
sum[i][j] = sum[i-1][j] + 1;
}
else {
sum[i][j] = 0;
}
}
}
}
inline void Query(int dp[]) {
long long area = 0;
for(int L = 1; L <= n; L++) {
while(!Stiva.empty()) {
Stiva.pop();
}
for(int i = 1; i <= m; i++) {
h[i] = sum[L][i];
while(!Stiva.empty() && h[Stiva.top()] >= h[i]) {
Stiva.pop();
}
if(!Stiva.empty()) {
St[i] = Stiva.top() + 1;
}
else {
St[i] = i;
}
Stiva.push(i);
}
while(!Stiva.empty()) {
Stiva.pop();
}
for(int i = m; i >= 1; i--) {
while(!Stiva.empty() && h[Stiva.top()] >= h[i]) {
Stiva.pop();
}
if(!Stiva.empty()) {
Dr[i] = Stiva.top() - 1;
}
else {
Dr[i] = i;
}
Stiva.push(i);
area = max(area, (Dr[i] - St[i] + 1) * 1LL * h[i]);
}
dp[L] = max(1LL * dp[L-1], area);
}
}
inline void Change() {
for(int i = 1; i <= n / 2; i++) {
for(int j = 1; j <= m; j++) {
swap(s[i][j], s[n - i + 1][j]);
}
}
Prec();
}
inline void Solve() {
for(int i = 1; i < n; i++) {
ans = max(ans, dpup[i] + dpdown[n - i]);
}
}
inline void Rotate(){
swap(n,m);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
s[i][j] = aux[j][n - i + 1];
}
}
}
int main()
{
Read();
Prec();
Query(dpup);
Change();
Query(dpdown);
Solve();
Rotate();
Prec();
Query(dpup);
Change();
Query(dpdown);
Solve();
g<< ans << "\n";
return 0;
}