Cod sursa(job #2008938)

Utilizator Mihai_PredaPreda Mihai Dragos Mihai_Preda Data 8 august 2017 00:34:09
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.03 kb
#include <iostream>
#include <fstream>
#include <stack>

using namespace std;

void Manacher(int v[], int sz, int ret[])
{
    int R = -1, C = 0, rad;
    for(int i = 1; i <= sz; ++i)
    {
        if(i <= R)
            rad = min(ret[2 * C - i], R - i) + 1;
        else
            rad = 0;
        while(i - rad >= 1 && i + rad <= sz && v[i-rad] == v[i+rad])
            rad++;
        ret[i] = rad - 1;
        if(i + ret[i] - 1 > R)
        {
            C = i;
            R = i + ret[i] - 1;
        }
    }
}

const int nMax = 1005;
const int mMax = 1005;

int n, m;
int a[nMax][mMax];
int pal[nMax][mMax];
int rasp;

void citire()
{
    ifstream in("dreptpal.in");
    in >> n >> m;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            in >> a[i][j];
    in.close();
}

int smallerSt[nMax], smallerDr[nMax];

void rezolvare()
{
    for(int i = 1; i <= n; ++i)
        Manacher(a[i], m, pal[i]);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            pal[i][j] = 2 * pal[i][j] + 1;
    for(int col = 1; col <= m; col++)
    {
        stack<pair<int, int> > st;
        st.push(make_pair(0, 0));
        for(int i = 1; i <= n; ++i)
        {
            while(pal[i][col] <= st.top().first)
                st.pop();
            smallerSt[i] = st.top().second;
            st.push(make_pair(pal[i][col], i));
        }

        while(st.empty() == false)
            st.pop();
        st.push(make_pair(0, n + 1));
        for(int i = n; i >= 1; --i)
        {
            while(pal[i][col] <= st.top().first)
                st.pop();
            smallerDr[i] = st.top().second;
            st.push(make_pair(pal[i][col], i));
        }

        for(int i = 1; i <= n; ++i)
            rasp = max(rasp, pal[i][col] * (smallerDr[i] - smallerSt[i] - 1));
    }
}

void afisare()
{
    ofstream out("dreptpal.out");
    out << rasp;
    out.close();
}

int main()
{
    citire();
    rezolvare();
    afisare();
    return 0;
}