Cod sursa(job #2582470)

Utilizator ivan.tudorIvan Tudor ivan.tudor Data 16 martie 2020 19:49:38
Problema DreptPal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int mat[N][N];
int p[N][N];
void manacher(int v[],int p[],int n){
  int c,r=0;
  v[0]=-5;
  v[n+1]=-10;
  for(int i=1;i<=n;i++){
    int rad=0;
    if(i<=r){
      rad=min(p[2*c-i],r-i);
    }
    while(v[i+rad+1]==v[i-rad-1])
      rad++;
    p[i]=rad;
    if(i+p[i]>r){
      c=i;
      r=i+p[i];
    }
  }
}
int stv[N];
int st[N];
int main()
{
  FILE*fin,*fout;
  fin=fopen("dreptpal.in","r");
  fout=fopen("dreptpal.out","w");
  int n,m;
  fscanf(fin,"%d%d",&n,&m);
  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
      fscanf(fin,"%d",&mat[i][j]);
    }
    manacher(mat[i],p[i],m);
  }
  int amax=0;
  for(int j=1;j<=m;j++){
    int vf=0;
    stv[vf]=0;
    p[0][j]=-1;
    for(int i=1;i<=n;i++){
      while(vf>0 && p[stv[vf]][j]>=p[i][j])
        vf--;
      st[i]=stv[vf];
      stv[++vf]=i;
    }
    vf=0;
    stv[vf]=n+1;
    p[n+1][j]=-1;
    for(int i=n;i>=1;i--){
      while(vf>0 && p[stv[vf]][j]>=p[i][j])
        vf--;
      int dr=stv[vf];
      if((dr-st[i]-1)*(2*p[i][j]+1)>amax){
        amax=(dr-st[i]-1)*(2*p[i][j]+1);
      }
      stv[++vf]=i;
    }
  }
  fprintf(fout,"%d",amax);
  return 0;
}