Pagini recente » Cod sursa (job #76290) | Cod sursa (job #2557059) | Cod sursa (job #2193897) | Cod sursa (job #577478) | Cod sursa (job #2670875)
#include <bits/stdc++.h>
#define DIM 1010
#define INF 2000000000
using namespace std;
class InParser {
private:
FILE *fin;
char *buff;
int sp;
char read_ch() {
++sp;
if (sp == 4096) {
sp = 0;
fread(buff, 1, 4096, fin);
}
return buff[sp];
}
public:
InParser(const char* nume) {
fin = fopen(nume, "r");
buff = new char[4096]();
sp = 4095;
}
InParser& operator >> (int &n) {
char c;
while (!isdigit(c = read_ch()) && c != '-');
int sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
} else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
InParser& operator >> (long long &n) {
char c;
n = 0;
while (!isdigit(c = read_ch()) && c != '-');
long long sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
} else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
};
int a[DIM][DIM],p[DIM][DIM*2],v[DIM*2],st[DIM],dr[DIM];
deque <int> d;
int n,m,i,j;
void manacher (int a[], int p[]){
int i, n = 0;
v[++n] = INF;
for (i=1;i<=m;++i){
v[++n] = a[i];
v[++n] = INF;
}
int Left = 0, Right = 0, c = 0;
for (i=1;i<=n;++i){
if (i > Right){
Left = Right = c = i;
p[i] = 1;
while (Left - 1 >= 1 && Right + 1 <= n && v[Left-1] == v[Right+1]){
p[i]++;
Left--, Right++;
}
} else {
int mirror = c - (i - c);
p[i] = min (p[mirror], Right - i + 1);
int st = i - p[i], dr = i + p[i];
while (st >= 1 && dr <= n && v[st] == v[dr]){
st--, dr++;
p[i]++;
}
if (i - p[i] + 1 < Left){
Left = i - p[i] + 1;
Right = i + p[i] - 1;
c = i;
}}}}
int main (){
InParser cin ("dreptpal.in");
ofstream cout ("dreptpal.out");
cin>>n>>m;
for (i=1;i<=n;++i){
for (j=1;j<=m;++j)
cin>>a[i][j];
manacher(a[i],p[i]);
}
int sol = 0;
for (j=1;j<=m;++j){
for (i=1;i<=n;++i)
v[i] = p[i][2*j] - 1;
d.clear();
for (i=1;i<=n;++i){
while (!d.empty() && v[i] <= v[d.back()])
d.pop_back();
if (d.empty())
st[i] = 1;
else st[i] = d.back() + 1;
d.push_back(i);
}
d.clear();
for (i=n;i;--i){
while (!d.empty() && v[i] <= v[d.back()])
d.pop_back();
if (d.empty())
dr[i] = n;
else dr[i] = d.back() - 1;
d.push_back(i);
}
for (i=1;i<=n;++i)
sol = max (sol,(dr[i] - st[i] + 1)*v[i] );
}
cout<<sol;
return 0;
}