Cod sursa(job #930125)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 27 martie 2013 14:14:03
Problema DreptPal Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include<fstream>
using namespace std;
int b[1010],a[1010][1010],pos[1010],v[1010],st,i,j,n,m,c,lim;

int main(void){
    ifstream fin("dreptpal.in");
    ofstream fout("dreptpal.out");
    fin>>n>>m; b[0]=-1; b[m+1]=-2;
    for (i=1; i<=n; ++i) {
        
        for (j=1; j<=m; ++j) fin>>b[j];
         
        c=0; lim=0;
        
        for (j=1; j<=m; ++j) {
            int pos=2*c-j;
             if (i<=lim) a[i][j]=min(a[i][pos],lim-i);
    
            while (b[j+a[i][j]+1]==b[j-a[i][j]-1]) ++a[i][j];
            
            if (j+a[i][j]>lim) { c=j; lim=j+a[i][j]; }
            
            }
    }
    
    int rez=n; v[0]=-1;
   for (j=2; j<m; ++j) {
       st=0; a[n+1][j]=-1;
       for (i=1; i<=n+1; ++i) {
           int col=a[i][j];
            if (col>v[st]) { ++st; v[st]=col; pos[st]=i; }
                  else if (col<v[st]) {
                               while (col<v[st]) {
                                if (v[st]*(i-pos[st])*2+i-pos[st]>rez) rez=2*v[st]*(i-pos[st])+i-pos[st];
                              --st;
                                 }
                              if (col>v[st]) { ++st; v[st]=col; }
                             }
                        }
      }
  
  fout<<rez;
 return(0);
}