Cod sursa(job #1046956)

Utilizator andreiiiiPopa Andrei andreiiii Data 3 decembrie 2013 19:00:48
Problema DreptPal Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <algorithm>
#include <fstream>
#include <string>
#include <stack>

using namespace std;

const int N=1003;

ifstream fin("dreptpal.in");
ofstream fout("dreptpal.out");

char cit[20*N];
vector <int> a;
int p[N][2*N], dr[N], st[N];
int n, m;

int solve()
{
    int i, j, sol=0;
    stack <int> s;
    for(j=1;j<=m;j++)
    {
        for(i=1;i<=n;i++)
        {
            while(!s.empty()&&p[s.top()][j]>=p[i][j])
            {
                dr[s.top()]=i-1;
                s.pop();
            }
            if(!s.empty()) st[i]=s.top()+1;
            else st[i]=1;
            s.push(i);
        }
        while(!s.empty())
        {
            dr[s.top()]=n;
            s.pop();
        }
        for(i=1;i<=n;i++) sol=max(sol, (p[i][j]*2+1)*(dr[i]-st[i]+1));
    }
    return sol;
}

int main()
{
    int i, j, x;
    char *l;
    fin>>n>>m; fin.get();
    for(i=1;i<=n;i++)
    {
        fin.getline(cit, 2*N);
        a.clear();
        a.push_back(-2);
        l=cit;
        for(j=1;j<=m;j++)
        {
            x=0;
            for(;*l>='0'&&*l<='9';l++) x=10*x+*l-'0'; l++;
            a.push_back(x);
        }
        a.push_back(-3);
        int c=0, r=0;
        for(j=1;j<a.size()-1;j++)
        {
            if(r>j) p[i][j]=min(r-j, p[i][2*c-j]);
            while(j+p[i][j]+1<a.size()&&j-p[i][j]-1>=0&&a[j+p[i][j]+1]==a[j-p[i][j]-1]) p[i][j]++;
            if(j+p[i][j]>r)
            {
                r=j+p[i][j];
                c=j;
            }
        }
        /*for(j=1;j<a.size()-1;j++)
        {
            //p[i][j]=(p[i][j]+1)/2;
            fout<<p[i][j]<<" ";
        }
        fout<<"\n";*/
    }
    m=a.size()-1;
    fout<<solve();

}