Pagini recente » Borderou de evaluare (job #804522) | Cod sursa (job #2262656) | Cod sursa (job #2086763) | Cod sursa (job #203061) | Cod sursa (job #2955090)
/// Preset de infoarena
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
const int maxN = 205;
int n, m, mat[maxN][maxN], st[maxN], dr[maxN], max_st[maxN], max_dr[maxN], max_sus[maxN], max_jos[maxN], v[maxN], ans;
string str;
int skyline(int x) /// RIP VARENA, YOU WILL FOREVER BE MISSED
{
vector <int> stiva;
for(int i = 1; i <= x; i++)
{
while(!stiva.empty() && v[stiva.back()] >= v[i])
stiva.pop_back();
if(stiva.empty())
st[i] = 1;
else
st[i] = stiva.back() + 1;
stiva.push_back(i);
}
stiva.clear();
for(int i = x; i >= 1; i--)
{
while(!stiva.empty() && v[stiva.back()] >= v[i])
stiva.pop_back();
if(stiva.empty())
dr[i] = x;
else
dr[i] = stiva.back() - 1;
stiva.push_back(i);
}
int arie = 0;
for(int i = 1; i <= x; i++)
arie = max(arie, v[i] * (dr[i] - st[i] + 1));
return arie;
}
int main()
{
fin >> n >> m;
for(int i = 1; i <= n; i++)
{
fin >> str;
for(int j = 1; j <= m; j++)
mat[i][j] = str[j - 1] - '0';
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if(mat[i][j] == 0)
v[j]++;
else
v[j] = 0;
}
max_sus[i] = max(max_sus[i - 1], skyline(m));
}
for(int i = 1; i <= m; i++)
v[i] = 0;
for(int i = n; i >= 1; i--)
{
for(int j = 1; j <= m; j++)
{
if(mat[i][j] == 0)
v[j]++;
else
v[j] = 0;
}
max_jos[i] = max(max_jos[i + 1], skyline(m));
}
for(int i = 1; i <= m; i++)
v[i] = 0;
for(int i = 1; i <= m; i++)
{
for(int j = 1; j <= n; j++)
{
if(mat[j][i] == 0)
v[j]++;
else
v[j] = 0;
}
max_st[i] = max(max_st[i - 1], skyline(n));
}
for(int i = 1; i <= n; i++)
v[i] = 0;
for(int i = m; i >= 1; i--)
{
for(int j = 1; j <= n; j++)
{
if(mat[j][i] == 0)
v[j]++;
else
v[j] = 0;
}
max_dr[i] = max(max_dr[i + 1], skyline(n));
}
for(int i = 1; i <= n; i++)
ans = max(ans, max_sus[i] + max_jos[i + 1]);
for(int i = 1; i <= m; i++)
ans = max(ans, max_st[i] + max_dr[i + 1]);
fout << ans;
return 0;
}