Cod sursa(job #2461100)

Utilizator FrostfireMagirescu Tudor Frostfire Data 24 septembrie 2019 21:26:36
Problema DreptPal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.27 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <cstring>
#include <stack>
#define NMAX 1000
#define inf 1000000000

using namespace std;

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

int n, m;
int a[NMAX+10][NMAX+10], v[NMAX+10], b[NMAX+10][NMAX+10], st[NMAX+10], dr[NMAX+10], sol;
vector <int> s;
stack <int> stiva;

int main()
{
    f >> n >> m;
    for(int i=1; i<=n; i++)
        {   for(int j=1; j<=m; j++)
                f >> a[i][j];
            memset(v, 0, sizeof(v));
            s.clear();
            int val1 = inf+1, val2 = inf+2, val3 = inf+3;
            s.push_back(val1);
            for(int j=1; j<=m; j++)
                {   s.push_back(val2);
                    s.push_back(a[i][j]);
                }
            s.push_back(val2);
            s.push_back(val3);

            int C=0, R=0;
            for(int j=1; j<s.size()-1; j++)
                {   int ogl = 2*C-j;
                    if(j < R) v[j] = min(R-j, v[ogl]);
                    while(s[j+v[j]+1] == s[j-v[j]-1]) v[j]++;
                    if(j+v[j] > R)
                        {   C = j;
                            R = j + v[j];
                        }
                }
            for(int j=2; j<=2*m; j+=2) b[i][j/2] = v[j] / 2 * 2 + 1;
        }
    for(int j=1; j<=m; j++)
        {   memset(st, 0, sizeof(st));
            memset(dr, 0, sizeof(dr));
            while(!stiva.empty()) stiva.pop();
            stiva.push(1);
            for(int i=2; i<=n; i++)
                {
                    while(!stiva.empty() && b[i][j] <= b[stiva.top()][j]) stiva.pop();
                    if(!stiva.empty()) st[i] = stiva.top();
                    else st[i] = 0;
                    stiva.push(i);
                }

            while(!stiva.empty()) stiva.pop();
            stiva.push(n);
            dr[n] = n+1;
            for(int i=n-1; i>=1; i--)
                {   while(!stiva.empty() && b[i][j] <= b[stiva.top()][j]) stiva.pop();
                    if(!stiva.empty()) dr[i] = stiva.top();
                    else dr[i] = n + 1;
                    stiva.push(i);
                }
            for(int i=1; i<=n; i++) sol = max(sol, b[i][j]*(dr[i]-st[i]-1));
        }
    g << sol << '\n';
    return 0;
}