Pagini recente » Cod sursa (job #1085170) | Cod sursa (job #1581840) | Cod sursa (job #2010113) | Cod sursa (job #2279249) | Cod sursa (job #2023384)
#include <fstream>
#include <stack>
using namespace std;
ifstream cin("dreptpal.in");
ofstream cout("dreptpal.out");
int n, m;
int mat[1010][1010];
int aux[2020];
int pali[2020][2020];
stack <int> S;
void citire(){
cin>>n>>m;
for (int i=1; i<=n; i++){
for (int j=1; j<=m; j++){
cin>>mat[i][j];
//cout<<mat[i][j]<<" ";
}
//cout<<'\n';
}
}
void make_pali(int line){
aux[0] = -2;
int pos = 1;
for (int i=1; i<=m; i++){
aux[pos++] = -1;
aux[pos++] = mat[line][i];
}
aux [pos++] = -1;
aux [pos] = -3;
/*cout<<"AUX de "<<line<<" :"<<'\n';
for (int i=0; i<=pos; i++){
cout<<aux[i]<<" ";
}
cout<<'\n';*/
pos--;
int R = 0;
int C = 0;
for (int i=1; i<=pos; i++){
int opus = C * 2 - i;
if (R > i){
pali[line][i] = min(pali[line][opus] , R - i);
}
while (aux[i + pali[line][i] + 1] == aux[i - pali[line][i] - 1]){
pali[line][i]++;
}
if (i + pali[line][i] > R){
R = i + pali[line][i];
C = i;
}
}
}
void test(){
for (int i=1; i<=n; i++){
for (int j=1; j<=m * 2 + 2; j++){
cout<<pali[i][j]<<" ";
}
cout<<'\n';
}
}
void strabunica(int col, int &MAX){
S.push(0);
pali[n+1][col] = 0;
for (int i=1; i<=n + 1; i++){
int val = pali[i][col];
while (!S.empty() && pali[S.top()][col] > val){
int nr = pali[S.top()][col];
S.pop();
MAX = max(MAX , nr * (i - S.top() - 1) );
}
S.push(i);
}
}
void solve(int &MAX){
int pm = m*2 + 2;
for (int i=1; i<=n; i++){
make_pali(i);
}
for (int i=1; i<=pm; i++){
strabunica(i , MAX);
}
//test();
}
int main() {
citire();
int MAX = 0;
solve(MAX);
cout<<MAX;
return 0;
}