Cod sursa(job #2801274)

Utilizator tomaionutIDorando tomaionut Data 15 noiembrie 2021 19:01:07
Problema DreptPal Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 kb

#include <bits/stdc++.h>

using namespace std;
ifstream fin("dreptpal.in");
ofstream fout("dreptpal.out");
int n, m;
int a[1005][1005];
int b[1005], st[1005], stg[1005], drp[1005];
int Solve()
{
    int i, top, ma = 0;
    top = 0;
    st[0] = 0;
    for (i = 1; i <= n; i++)
    {
        while (b[st[top]] >= b[i])
            top--;
        stg[i] = i - st[top];
        st[++top] = i;
    }

    top = 0;
    st[0] = n + 1;
    for (i = n; i >= 1; i--)
    {
        while (b[st[top]] >= b[i])
            top--;
        drp[i] = st[top] - i;
        st[++top] = i;
    }
    for (i = 1; i <= n; i++)
        ma = max(ma, (stg[i] + drp[i] - 1) * b[i]);
    return ma;
}
int main()
{
    int i, j, x, y, ma = 0;
    fin >> n >> m;
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= m; j++)
            fin >> b[j];

        for (j = 1; j <= m; j++)
        {
            x = y = j;
            while (b[x] == b[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++)
            b[i] = a[i][j];
        ma = max(ma, Solve());
    }
    fout << ma;


    return 0;
}