Cod sursa(job #2311978)

Utilizator mirunaFmiruna mirunaF Data 3 ianuarie 2019 22:40:37
Problema DreptPal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <algorithm>
#include <iostream>
#include <fstream>

using namespace std;

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

#define N 1005

int v[N][N], l[N][2*N];
int st_val[N], st_nr[N];
int n, m, bst_sol;

void read ()
{
    int i, j;
    in >> n >> m;
    for ( i = 1; i <= n; ++i)
        for ( j = 1; j <= m; ++j)
            in >> v[i][j];
}

void solve ()
{
    int i, j, st, dr, vf, nr;
    for ( i = 1; i <= n; ++i)
    {
        st = 1;
        dr = 1;
        for ( j = 2; j <= m; ++j)
            if (j > dr)
            {
                st = dr = j;
                for ( ; v[i][st-1] == v[i][dr+1] && st > 1 && dr < m; --st, ++dr)
                    ++l[i][j];
            }
            else
            {
                l[i][j] = min ( l[i][st + dr - j], dr - j );
                if (j + l[i][j] == dr)
                {
                    st = j - l[i][j];
                    dr = j + l[i][j];
                    for ( ; v[i][st - 1] == v[i][dr +1 ] && st > 1 && dr < m; --st, ++dr)
                        ++l[i][j];
                }
            }
    }

    for ( j = 1; j <= m; ++j )
    {
        vf = 0;
        for ( i = 1; i <= n; ++i)
        {
            nr = 0;
            while ( vf && l[i][j] <= st_val[vf] )
            {
                nr += st_nr[vf];
                bst_sol = max ( bst_sol,(( st_val[vf] << 1 ) | 1) * nr );
                --vf;
            }
            st_val[++vf] = l[i][j];
            st_nr[vf] = ++nr;
        }
        nr = 0;
        while (vf)
        {
            nr += st_nr[vf];
            bst_sol = max ( bst_sol,((st_val[vf] << 1) | 1) * nr);
            --vf;
        }
    }

    out << bst_sol;
}

int main ()
{
    read ();
    solve ();

    in.close();
    out.close();

    return 0;
}