Pagini recente » Cod sursa (job #400999) | Cod sursa (job #563227) | Cod sursa (job #3261827) | Cod sursa (job #627823) | Cod sursa (job #2552210)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("dreptpal.in");
ofstream fout("dreptpal.out");
int a[1010][1010];
int t[1010];
int st[1010];
int s[1010], d[1010];
int n, m, top;
int calcul()
{
int i;
t[n + 1] = -1;
st[0] = 0;
top = 0;
for(i = 1;i <= n;i++)
{
while(t[st[top]] >= t[i])
top--;
s[i] = i - st[top];
st[++top] = i;
}
top = 0;
st[0] = n + 1;
for(i = n;i >= 1;i--)
{
while(t[st[top]] >= t[i])
top--;
d[i] = st[top] - i;
st[++top] = i;
}
int M = 0;
for(i = 1;i <= n;i++)
M = max(M, (s[i] + d[i] - 1) * t[i]);
return M;
}
int main()
{
int i, j, x, y, amax = 0;
fin >> n >> m;
t[0] = -1;
t[m + 1] = -2;
for(i = 1;i <= n;i++)
{
/// citire linie
for(j = 1;j <= m;j++)
fin >> t[j];
/// pentru fiecare element a[i][j] aflam lungimea
/// maxima a unui palindrom centrat in j pe linia i
for(j = 1;j <= m;j++)
{
x = y = j;
while(t[x] == t[y])
{
x--;
y++;
}
a[i][j] = y - x - 1;
}
}
for(j = 1;j <= m;j++)
{
/// memorez fiecare coloana in t[]
for(i = 1;i <= n;i++)
t[i] = a[i][j];
/** Aflu aria maxima a unei submatrice
care are centrul pe coloana j.
Acest lucru il facem cu o stiva pentru a
afla pentru fiecare t[i] care este secventa
maximala care-l contine pe t[i] si are pe t[i] minim
*/
x = calcul();
amax = max(amax, x);
}
fout << amax;
return 0;
}