Cod sursa(job #2008697)

Utilizator Mihai_PredaPreda Mihai Dragos Mihai_Preda Data 7 august 2017 13:56:57
Problema DreptPal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include <iostream>
#include <fstream>
#include <stack>

using namespace std;

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

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;
}