Cod sursa(job #3350575)

Utilizator unomMirel Costel unom Data 9 aprilie 2026 19:45:17
Problema DreptPal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.27 kb
#include <fstream>
#include <iostream>
#include <stack>

using namespace std;

ifstream in("dreptpal.in");
ofstream out("dreptpal.out");
int n, m;
int v[1005][1005];
int man[1005][1005];
int st[1005][1005];
int dr[1005][1005];

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

        v[i][0] = -1;
        v[i][m + 1] = -2;

        int l = 1;
        int r = 1;
        for(int j = 1; j<=m; j++)
        {
            man[i][j] = max(0, min(r - j, man[i][l + (r - j)]));

            while(v[i][j - man[i][j]] == v[i][j + man[i][j]])
            {
                man[i][j]++;
            }

            if(j + man[i][j] > r)
            {
                l = j - man[i][j];
                r = j + man[i][j];
            }

//            cout<<man[i][j]<<" ";
        }
//        cout<<'\n';

        for(int j = 1; j<=m; j++)
        {
            man[i][j] = 2 * man[i][j] - 1;
        }
    }

    int ans = 0;
    stack<int> s;
    for(int j = 1; j<=m; j++)
    {
        while(!s.empty())
        {
            s.pop();
        }
        for(int i = 1; i<=n; i++)
        {
            while(!s.empty() && man[s.top()][j] >= man[i][j])
            {
                s.pop();
            }

            if(s.empty())
            {
                st[i][j] = 0;
            }
            else
            {
                st[i][j] = s.top();
            }
            s.push(i);
        }


        while(!s.empty())
        {
            s.pop();
        }
        for(int i = n; i>=1; i--)
        {
            while(!s.empty() && man[s.top()][j] >= man[i][j])
            {
                s.pop();
            }

            if(s.empty())
            {
                dr[i][j] = n + 1;
            }
            else
            {
                dr[i][j] = s.top();
            }
            s.push(i);
        }

        for(int i = 1; i<=n; i++)
        {
            int cur = (dr[i][j] - st[i][j] - 1) * man[i][j];

//            cout<<i<<" "<<j<<" -> "<<cur<<'\n';
//            cout<<st[i][j]<<" "<<dr[i][j]<<'\n';

            ans = max(ans, cur);
        }
    }

    out<<ans;

    return 0;
}