Cod sursa(job #2801272)

Utilizator tomaionutIDorando tomaionut Data 15 noiembrie 2021 18:59:22
Problema DreptPal Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("dreptpal.in");
ofstream fout("dreptpal.out");
int n, m,a[1005][1005],t[1005],solst[1005],soldr[1005],ans;
int st[1005],top;
int main()
{
    int i, j,x,y;
    fin >> n >> m;
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= m; j++)
            fin >> t[j];
        for (j = 1; j <= m; j++)
        {
            x = y = j;
            while (t[x] == t[y] and x > 0 and y <= m)
            {
                x--;
                y++;
            }
            a[i][j] = y - x - 1;
        }
    }
    for (j = 1; j <= m; j++)
    {
        for (i = 1; i <= n; i++)
            t[i] = a[i][j];
        st[0] = 0;
        top = 0;
        for (i = 1; i <= n; i++)
        {
            x = t[i];
            while (x <= t[st[top]])
                top--;
            solst[i] = i - st[top];
            st[++top] = i;
        }
        st[0] = n + 1;
        top = 0;
        for (i = n; i >= 1; i--)
        {
            x = t[i];
            while (x <= t[st[top]])
                top--;
            soldr[i] = st[top] - i;
            st[++top] = i;
        }
        for (i = 1; i <= n; i++)
            ans = max(ans, (solst[i] + soldr[i] - 1) * t[i]);
    }
    fout << ans;
    return 0;
}