Cod sursa(job #2663489)

Utilizator ptudortudor P ptudor Data 26 octombrie 2020 16:10:45
Problema DreptPal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.67 kb
#include<bits/stdc++.h>
#define fore(start,i,end) for(int i = start; i <= end; i++)
#define dbg(x)  #x << "=" << x << " "
#define dbg2(x,y)  "{" << x << "," << y << "} "
#define dbg3(x,y,k) "{" << x << "," << y << "," << k << "} "
#define dbg4(x,y,k,j) "{" << x << "," << y << "," << k << " , " << j << "} "

#define ll long long
#define f1 first
#define f2 second
#define inf 1000000005
#define debug_st(st) if (true) {cout << #st << " : "; stack<int> s123; while (!s123.empty()) cout << s123.top() << " ", s123.pop(); cout << "\n";}
#define debug_a(a,n) cout << #a << " : "; for(int i = 1; i <= n; i++) cout << a[i] << " "; cout << "\n";
#define debug_m(a,n,m) cout << #a << " :\n"; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++) cout << a[i][j] << " "; cout << "\n"; }cout << "\n";
#define debug_v(v) cout << #v << " : "; for(auto k : v) cout << k << " "; cout << "\n";
#define debug_s(s) cout << #s << " : "; for (auto k : s) cout << k < " "; cout << "\n";
#define debug_s2(s) cout << #s << " : "; for(auto k : s) cout << dbg2((*k).first,(*k).second); cout << "\n";
#define nmax 1005



using namespace std;

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

ll a[nmax][nmax],n,m,p[nmax][nmax],v[nmax],sol;
ll Extend(ll i, ll bonus, ll v[nmax])
{
   //cout << "EXTEND i = " << i << "\n";
    ll p = i + bonus + 1,poz = i + bonus;
    while (p <= m && v[p] == v[i - (p - i)])
    {
        poz = p++;
    }
    //cout << "poz = " << poz << "\n";
    return poz;
}
void get_p(ll v[nmax],ll p[nmax])
{ll i;
    ll mij = 0,dr = 0;
    for (i = 1; i <= m; i++)
    {
        ///daca dr este in spatele nostru, ne exstindem cat putem, clar
        ///daca dr este dupa i
        /// dr  i  mij  i  dr p[i] = p[mij - (i - mij)] dupaia daca e mai mare de dr
        ///il putem extinde

        if (dr < i)
        {
            int poz = Extend(i , 0 , v); /// cate de mult se poate extinde.
            p[i] = (poz - i + 1);
            mij = i;
            dr = poz;
        }
        else
        {
            p[i] = p[mij - (i - mij)];
            if (i + p[i] < dr)
            {
                continue;
            }
            p[i] = min(p[i] , dr - i + 1);
            int poz = Extend(i , p[i] - 1 , v);
            dr = poz;
            p[i] = poz - i + 1;
            mij = i;
        }
    }
   // debug_a(v , m);
   // debug_a(p ,m);cout << "\n\n";
}
stack<ll> q;
ll st[nmax],dr[nmax];
void solve(ll v[nmax],ll col)
{ll i;
    while (!q.empty())q.pop();
    for (i = 1; i <= n; i++)
    {
        while (!q.empty() && v[i] < v[q.top()])
        {
            q.pop();
        }
        if (q.empty())
            st[i] = i;
        else
            st[i] = i - q.top();
        q.push(i);
    }

    while (!q.empty())q.pop();
    for (i = n; i >= 1; i--)
    {
        while (!q.empty() && v[i] < v[q.top()])
        {
            q.pop();
        }
        if (q.empty())
        {
            dr[i] = n - i +1;
        }
        else
            dr[i] = q.top() - i;
    }
    for (i = 1; i <= n; i++)
    {
        sol = max(sol , p[i][col] * (st[i] + dr[i] - 1));
    }
    //debug_a(v , n);
   // for (i = 1; i <= n; i++)
   // {
    //    cout << dbg(i) << dbg(st[i])<< dbg(dr[i]) << "\n";
   // }cout << "\n";
}
int main()
{ll i,j;
    in >> n >> m;
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= m; j++)
        in >> a[i][j];
    }
    for (i = 1; i <= n; i++)
    {
        get_p(a[i],p[i]);
    }

    for (j = 1; j <= m; j++)
    {
        for (i = 1; i <= n; i++)
        {
            v[i] = a[i][j];
        }
        solve(v,j);
    }out << sol << "\n";

}