Pagini recente » Cod sursa (job #2745911) | Cod sursa (job #2740131) | Cod sursa (job #928766) | Cod sursa (job #1304928) | Cod sursa (job #3350575)
#include <fstream>
#include <iostream>
#include <stack>
using namespace std;
ifstream in("dreptpal.in");
ofstream out("dreptpal.out");
int n, m;
int v[1005][1005];
int man[1005][1005];
int st[1005][1005];
int dr[1005][1005];
int main()
{
in>>n>>m;
for(int i = 1; i<=n; i++)
{
for(int j = 1; j<=m; j++)
{
in>>v[i][j];
}
v[i][0] = -1;
v[i][m + 1] = -2;
int l = 1;
int r = 1;
for(int j = 1; j<=m; j++)
{
man[i][j] = max(0, min(r - j, man[i][l + (r - j)]));
while(v[i][j - man[i][j]] == v[i][j + man[i][j]])
{
man[i][j]++;
}
if(j + man[i][j] > r)
{
l = j - man[i][j];
r = j + man[i][j];
}
// cout<<man[i][j]<<" ";
}
// cout<<'\n';
for(int j = 1; j<=m; j++)
{
man[i][j] = 2 * man[i][j] - 1;
}
}
int ans = 0;
stack<int> s;
for(int j = 1; j<=m; j++)
{
while(!s.empty())
{
s.pop();
}
for(int i = 1; i<=n; i++)
{
while(!s.empty() && man[s.top()][j] >= man[i][j])
{
s.pop();
}
if(s.empty())
{
st[i][j] = 0;
}
else
{
st[i][j] = s.top();
}
s.push(i);
}
while(!s.empty())
{
s.pop();
}
for(int i = n; i>=1; i--)
{
while(!s.empty() && man[s.top()][j] >= man[i][j])
{
s.pop();
}
if(s.empty())
{
dr[i][j] = n + 1;
}
else
{
dr[i][j] = s.top();
}
s.push(i);
}
for(int i = 1; i<=n; i++)
{
int cur = (dr[i][j] - st[i][j] - 1) * man[i][j];
// cout<<i<<" "<<j<<" -> "<<cur<<'\n';
// cout<<st[i][j]<<" "<<dr[i][j]<<'\n';
ans = max(ans, cur);
}
}
out<<ans;
return 0;
}