Cod sursa(job #2667586)

Utilizator tomaionutIDorando tomaionut Data 3 noiembrie 2020 17:41:34
Problema DreptPal Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 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;
}