Pagini recente » Cod sursa (job #235063) | Cod sursa (job #2256165) | Cod sursa (job #2256150) | Cod sursa (job #817317) | Cod sursa (job #2065379)
#include <fstream>
#include <deque>
#define DIM 202
using namespace std;
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
int n, m, frecv[DIM], a[DIM][DIM], isus[DIM], ijos[DIM], last[DIM], first[DIM], jsus[DIM], jjos[DIM];
deque<int> c;
void drmax(int i, int tip){
int ariemax = 0;
c.clear();
c.push_back(0);
int cnt = 0;
if(tip <= 2)
cnt = m;
else
cnt = n;
for(int j = 1; j <= cnt + 1; ++ j){
while(!c.empty() && frecv[c.back()] >= frecv[j]){
last[c.back()] = j - 1;
c.pop_back();
}
if(frecv[j])
first[j] = c[c.size() - 1] + 1;
c.push_back(j);
}
for(int j = 1; j <= cnt; ++ j)
ariemax = max(ariemax, (last[j] - first[j] + 1) * frecv[j]);
if(tip == 1)
isus[i] = max(isus[i - 1], ariemax);
if(tip == 2)
ijos[i] = max(ijos[i + 1], ariemax);
if(tip == 3)
jsus[i] = max(jsus[i - 1], ariemax);
if(tip == 4)
jjos[i] = max(jjos[i + 1], ariemax);
}
void resetfrecv(){
for(int i = 1; i <= m; ++ i)
frecv[i] = 0;
}
int main()
{
f>>n>>m;
char ch;
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= m; ++ j){
f>>ch;
a[i][j] = ch - '0';
}
for(int i = 1; i <= n; ++ i){
for(int j = 1; j <= m; ++ j)
if(a[i][j])
frecv[j] = 0;
else
++ frecv[j];
drmax(i, 1);
}
resetfrecv();
for(int i = n; i >= 1; -- i){
for(int j = 1; j <= m; ++ j)
if(a[i][j])
frecv[j] = 0;
else
++ frecv[j];
drmax(i, 2);
}
int Aria = -1;
for(int i = 1; i < n; ++ i)
Aria = max(Aria, isus[i] + ijos[i + 1]);
resetfrecv();
for(int i = 1; i <= m; ++ i){
for(int j = 1; j <= n; ++ j)
if(a[j][i])
frecv[j] = 0;
else
++ frecv[j];
drmax(i, 3);
}
resetfrecv();
for(int i = m; i >= 1; -- i){
for(int j = 1; j <= n; ++ j)
if(a[j][i])
frecv[j] = 0;
else
++ frecv[j];
drmax(i, 4);
}
for(int i = 1; i < m; ++ i)
Aria = max(Aria, jsus[i] + jjos[i + 1]);
g<<Aria<<'\n';
return 0;
}