Pagini recente » Cod sursa (job #2968020) | Cod sursa (job #1173387) | Cod sursa (job #2883886) | Cod sursa (job #2671880) | Cod sursa (job #2017304)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("dreptpal.in");
ofstream g("dreptpal.out");
const int MaxN = 1002;
int pal[MaxN][MaxN], mat[MaxN][MaxN];
void Manacher(int n, int m){
for(int i = 1; i <= n; ++i){
int mij = 0;
for(int j = 1; j <= m; ++j){
if(j <= mij + pal[i][mij]){
pal[i][j] = min(mij + pal[i][mij] - j, pal[i][mij-(j-mij)]);
}
while(j - pal[i][j] > 1 && j + pal[i][j] < m && mat[i][j+pal[i][j]+1] == mat[i][j-pal[i][j]-1]) ++ pal[i][j];
if(j + pal[i][j] >= mij + pal[i][mij]){
mij = j;
}
}
}
}
int strabunica(vector <int> v){
int ans = -1;
stack <int> stiva;
stiva.push(0);
int i = 0;
while(i < v.size()){
while(v[i] < v[stiva.top()] && stiva.size() > 1){
int vf = v[stiva.top()];
stiva.pop();
ans = max(ans, vf*(i-stiva.top()-1));
}
stiva.push(i);
++i;
}
return ans;
}
int main(){
int n, m;
f >> n >> m;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
f >> mat[i][j];
}
}
Manacher(n, m);
int ans = -1;
for(int i = 1; i <= m; ++i){
vector <int> v;
v.push_back(0);
for(int j = 1; j <= n; ++j){
v.push_back(2*pal[j][i]+1);
}
v.push_back(0);
ans = max(ans,strabunica(v));
}
g << ans;
return 0;
}